Fork me on GitHub

算法-点分治

Posted on | Edited on | In

解决树上路径问题

在解决树上路径问题时，我们会想到将树拆成几部分来提高我们的时间效率，当一棵树被分成若干子树时，我们可以用同样的方法进行处理，并不断进行下去，所以为了使每次的处理最优，我们通常要选取树的重心进行处理，选取了重心我们的下一层子树节点数会更小，时间复杂度也就更优秀。

  • 重心:一个点为重心，则它所连接的子树节点数最大值最小

变量定义

变量名 含义
rt 当前子树根节点
siz_tree 当前子树大小
F 以每个节点为根的最大子树大小

1.寻找重心

  • DFS出以每个点为根的最大子树大小
  • 如果当前节点为根更优，更新当前节点为根
1
2
3
4
5
6
7
8
9
10
11
12
void getroot(int u, int fa) {
  siz[u] = 1, F[u] = 0;
  for (int i = head[u]; i; i = E[i].next) {
    int v = E[i].v;
    if (v == fa || vis[v]) continue;
    getroot(v, u);
    siz[u] += siz[v];
    F[u] = max(F[u], siz[v]);
  }
  F[u] = max(F[u], siz_tree - siz[u]);
  if (F[u] < F[rt]) rt = u;
}

2.更新

对于一棵树的重心，优先考虑经过这个点的路径对答案的贡献(work统计，由题意而定)

3.继续递归

删去已经计算过的重心(vis标记)，继续递归其子树

1
2
3
4
5
6
7
8
9
10
11
void solve(int u) {
  vis[u] = 1;
  work(u);
  for (int i = head[u]; i; i = E[i].next) {
    int v = E[i].v;
    if (vis[v]) continue;
    F[rt = 0] = siz_tree = siz[v];
    getroot(v, 0);
    solve(rt);
  }
}
  • 完成所有的solve操作后，就可以得到想要的答案了
  • 因为每一次寻找子树的大小不超过 $n/2$ 所以分治层数不超过 $logn$ 所以总复杂度 $nlogn$

练习题

  • POJ 1741
  • BZOJ 1316
  • BZOJ 14680
  • BZOJ 2152
  • BZOJ 2599