边分治原理及实现

边分治原理及实现

树分治系列:

概述

点分治是一种分治策略,其核心在于寻找子树的中心边,从中心边的两个点分治解决,从而优化复杂度,实现O(\log n)的分治复杂度(不含分治中的处理复杂度)。

原理与实现

重构树(非必须)

由于某些树对边分治不利(例如:深度只有1的树/菊花图),我们需要重构树。重构后的树满足一个点的度数不超过3,即为一棵二叉树。
重构树的过程是,先将儿子的重构解决完毕,再将儿子二分接到虚点上,虚点的设置需要不影响之后的答案计算。

inline void rebuild(int u, int fa) {
    int ff = 0;
    for(int i = heado[u]; ~i; i = grao[i].nxt) {
        int v = grao[i].to, w = grao[i].w;
        if(v == fa) continue;
        if(!ff) {
            addedge(u, v, w);
            addedge(v, u, w);
            ff = u;
        } else {
            int k = ++n;
            addedge(ff, k, 0);
            addedge(k, ff, 0);
            addedge(k, v, w);
            addedge(v, k, w);
            ff = k;
        }
        rebuild(v, u);
    }
}

找中心边

分治的第一步是找到重心。中心边是指树中满足两个端点对应子树中较大的大小最小的边,这样的边满足其端点子树大小分布比较平衡,可以更好地缩小问题规模。在实际操作中,我们设计递归算法,将一个边的左右两个子树统计出来。递归的时候注意将当前中心边打上删除标记,避免统计串子树了。

inline void findct(int u, int fa) {
    siz[u] = 1;
    for(int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(del[i >> 1] || v == fa) continue;
        findct(v, u);
        siz[u] += siz[v];
        int vsiz = std::max(siz[v], sum - siz[v]);
        if(vsiz < ctsiz) {
            ct = i;
            ctsiz = vsiz;
        }
    }
}

处理问题的流程

既然是分治,我们就要考虑分治的流程。

  1. 找到两个子树的中心边,递归到子树中心边去解决子问题
  2. 将子树的答案合并至当前树根

例题:点连接去看:SPOJ – QTREE4

参考资料



1 thought on “边分治原理及实现”

发表评论

您的电子邮箱地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据