树分治系列：

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

原理与实现

重构树（非必须）

由于某些树对边分治不利（例如：深度只有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