dsu，对于无修改子树信息查询，并且操作支持undo的问题
暴力dfs，对于每个节点，对所有轻儿子dfs下去，然后再消除轻儿子的影响
dfs重儿子，然后dfs暴力恢复轻儿子们的影响，再把当前节点影响算进去
就有了整棵子树的信息了，时间复杂度O(nlogn)
经典例题:http://codeforces.com/contest/600/problem/E
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 typedef long long ll; 6 7 const int N = 1e5 + 5; 8 9 int n, c[N]; 10 11 int cnt[N], maxCnt; 12 13 int siz[N], son[N]; 14 15 vector <int> e[N]; 16 17 ll ans[N], sum[N]; 18 19 void dfs1(int u, int fr) { 20 siz[u] = 1; 21 for (int v : e[u]) { 22 if (v == fr) continue; 23 dfs1(v, u); 24 siz[u] += siz[v]; 25 if (siz[v] > siz[son[u]]) son[u] = v; 26 } 27 } 28 29 void update(int x, int y) { 30 sum[cnt[x]] -= x; 31 cnt[x] += y; 32 sum[cnt[x]] += x; 33 if (cnt[x] > maxCnt) maxCnt = cnt[x]; 34 if (sum[maxCnt] == 0) maxCnt --; 35 } 36 37 void dfs3(int u, int fr, int val) { 38 update(c[u], val); 39 for (int v : e[u]) { 40 if (v == fr) continue; 41 dfs3(v, u, val); 42 } 43 } 44 45 void dfs2(int u, int fr) { 46 for (int v : e[u]) { 47 if (v == fr || v == son[u]) continue; 48 dfs2(v, u), dfs3(v, u, -1); 49 } 50 if (son[u]) dfs2(son[u], u); 51 for (int v : e[u]) { 52 if (v == fr || v == son[u]) continue; 53 dfs3(v, u, 1); 54 } 55 update(c[u], 1); 56 ans[u] = sum[maxCnt]; 57 } 58 59 int main() { 60 ios::sync_with_stdio(false); 61 cin >> n; 62 for (int i = 1; i <= n; i ++) 63 cin >> c[i]; 64 for (int u, v, i = 1; i < n; i ++) { 65 cin >> u >> v; 66 e[u].push_back(v); 67 e[v].push_back(u); 68 } 69 dfs1(1, 1), dfs2(1, 1); 70 for (int i = 1; i <= n; i ++) 71 cout << ans[i] << ' '; 72 cout << endl; 73 return 0; 74 }
长链剖分，选择深度大的儿子作为重儿子
O(1)继承重儿子信息，然后按深度合并轻儿子信息
因为每个节点被作为轻链节点只会被合并一次，所以O(n)
例题:http://codeforces.com/problemset/problem/1009/F
1 /* 长链剖分,选择深度最大的儿子作为重儿子,用于合并以深度为下标的信息 2 * 像 dsu 一样,直接继承重儿子信息,然后按深度暴力合并其他儿子信息 3 * 时间复杂度考虑每个节点作为轻儿子里的节点被合并只会有一次,所以 O(n) 4 * 另一种用法,可以 O(nlogn) 预处理后,O(1) 找到 k 级祖先 5 */ 6 int n; 7 int len[N], son[N], ans[N]; 8 vector <int> e[N]; 9 int tmp[N], *ptr, *f[N]; 10 void dfs(int u, int fr) { 11 for (int v : e[u]) { 12 if (v == fr) continue; 13 dfs(v, u); 14 if (len[v] > len[son[u]]) son[u] = v; 15 } 16 len[u] = len[son[u]] + 1; 17 } 18 void dp(int u, int fr) { 19 f[u][0] = 1; 20 if (son[u]) { 21 f[son[u]] = f[u] + 1; 22 dp(son[u], u); 23 ans[u] = ans[son[u]] + 1; 24 } 25 for (int v : e[u]) { 26 if (v == son[u] || v == fr) continue; 27 f[v] = ptr, ptr += len[v]; 28 dp(v, u); 29 for (int j = 0; j < len[v]; j ++) { 30 f[u][j + 1] += f[v][j]; 31 if ((f[u][j + 1] > f[u][ans[u]]) || (f[u][j + 1] == f[u][ans[u]] && j + 1 < ans[u])) 32 ans[u] = j + 1; 33 } 34 } 35 if (f[u][0] >= f[u][ans[u]]) ans[u] = 0; 36 } 37 int main() { 38 in(n); 39 for (int u, v, i = 1; i < n; i ++) { 40 in(u), in(v); 41 e[u].push_back(v); 42 e[v].push_back(u); 43 } 44 dfs(1, 1); 45 f[1] = ptr = tmp, ptr += len[1]; 46 dp(1, 1); 47 for (int i = 1; i <= n; i ++) 48 printf("%d ", ans[i]); 49 return 0; 50 }
区分几种算法(dsu，树链剖分，树分治)用途:
树链剖分分为重链剖分和长链剖分
重链剖分应用比较多也比较常见不再赘述
当然dsu虽然也是一种应用但还是拿出来提一下把
下面的树分治仅仅针对点分治
dsu，长链剖分，点分治
三种都是无修改的树上信息查询算法
dsu应用限制:
只能统计子树中所有点的信息，并且操作必须支持删除
所以无法维护链的信息
长链剖分应用限制:
因为一般用于基于深度的信息合并
所以无法维护子树全部信息，只能维护深度相关信息
所以对于有边权的树一般都没有办法
树分治应用限制：
多用来树上路径的统计计数
缺点是无法像上述两种算法O(1)继承某个儿子的信息
所以可维护的信息种类相对有限