边分治原理及实现
树分治系列：
概述
点分治是一种分治策略，其核心在于寻找子树的中心边，从中心边的两个点分治解决，从而优化复杂度，实现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;
}
}
}
处理问题的流程
既然是分治，我们就要考虑分治的流程。
- 找到两个子树的中心边，递归到子树中心边去解决子问题
- 将子树的答案合并至当前树根
