浅谈静态树链问题

开始前先进行一个全民投票吧！
投票：遇到静态树链问题，你会选择（点击选项进行投票）：
1、直接树链剖分！

2、其他在线算法？

3、考虑离线算法。

4、本蒟蒻不会……

简介

本文主要讨论静态的树链问题。树链问题，可以看作树上的区间问题，这个区间可以看作一个结点 \(u\) 到另一个结点 \(v\) 所经最短路径形成的序列。这种问题大多需要用树链剖分来解决，但树链剖分会在解决对应区间问题的数据结构上增加一个 \(\log\)，这无疑会大大增加算法的常数压力，因此本文将在静态树链问题上讨论其他解法。
由于作者能力有限，因此仅提供了三道例题，而且知道的解法并不多，因此本文的代码量十分饱满，理论方面的讲解对新人比较不友好，也希望大家能够提出其他高效的思路和建议。
例题一：树链求和

解法一：树链剖分

思路非常简单，就是纯粹的树链剖分，由于没有修改操作，可以直接跑前缀和，然后以 \(O(1)\) 的复杂度完成每次子区间查询，单次查询的时间复杂度为 \(O(\log n)\)。
这种做法的时间复杂度主要看查询的数据结构，在遇到复杂的静态树链问题上并不吃香，很容易被卡常。
参考代码如下：

1. #include<bits/stdc++.h>
2. using namespace std;
3. //#define int long long
4. #define I_love_Foccarus return
5. #define rep(i,a,b) for(int i=a;i<=b;i++)
6. #define deap(i,a,b) for(int i=a;i>=b;i--)
7. #define in(a) a=read()
8. #define fi first
9. #define se second
10. const int N = 1e5 + 5;
11. const int inf = INT_MAX;
12. inline int read() { //浓缩后的快读        
13.     int x=0,f=1,ch=getchar();
14.         while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
15.         while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
16.         I_love_Foccarus x*f;
17. }
18. struct Edge { //链式前向星存树
19.         int act , nex;
20. } edge[N];
21. int head[N] , eid;
22. void eadd(int u , int v) {
23.         edge[++eid].act = v , edge[eid].nex = head[u] , head[u] = eid;
24. }
25. int c[N] , a[N];
26. int sz[N] , w[N] , top[N] , dfn[N] , dfm[N] , dep[N] , fa[N], vis;
27. void dfsw(int u,int father) { //求重链
28.         sz[u] = 1;
29.         dep[u] = dep[father] + 1;
30.         for(int i = head[u] ; i ; i = edge[i].nex) {
31.                 int v = edge[i].act;
32.                 dfsw(v , u);
33.                 sz[u] += sz[v];
34.                 if(sz[v] > sz[w[u]]) w[u] = v;
35.         }
36. }
37. void dfs(int u , int ftop) { //树链剖分
38.         dfn[u] = ++vis , dfm[vis] = u , top[u] = ftop;
39.         if(w[u]) dfs(w[u] , ftop);
40.         for(int i = head[u] ; i ; i = edge[i].nex) {
41.                 int v = edge[i].act;
42.                 if(v == w[u]) continue;
43.                 dfs(v , v);
44.         }
45. }
46. int query(int x , int y) { //查询
47.         int ans = 0;
48.         while(top[x] != top[y]) {
49.                 if(dep[top[x]] < dep[top[y]]) swap(x , y);
50.                 ans += c[dfn[x]] - c[dfn[top[x]] - 1]; //统计子区间和
51.                 x = fa[top[x]];
52.         }
53.         if(dfn[x] < dfn[y]) swap(x , y);
54.         ans += c[dfn[x]] - c[dfn[y] - 1];
55.         I_love_Foccarus ans;
56. }
57. signed main() {
58.         int n , root;
59.         in(n);
60.         rep(i , 1 , n)in(a[i]);
61.         rep(i , 1 , n) {
62.                 in(fa[i]);
63.                 if(fa[i] != i)eadd(fa[i] , i);
64.                 else root = i;
65.         }
66.         dfsw(root , 0);
67.         dfs(root , 0);
68.         rep(i , 1 , n)c[i] = c[i - 1] + a[dfm[i]]; //前缀和初始化
69.         int q;
70.         in(q);
71.         while(q--){
72.                 int u , v;
73.                 in(u) , in(v);
74.                 printf("%d\n",query(u , v));
75.         }
76.         I_love_Foccarus 0;
77. }

复制代码

解法二：容斥原理（树上差分）

不难发现，查询的内容可减，因此可以先通过一轮 dfs 求出每个结点到根结点的路径形成的序列的序列和，用一个数组 \(f\) 储存下来。
然后举个例子，如图，查询 \(3,5\)：

不难发现 \(f_{\operatorname{LCA}(u,v)}\) 被计算了两次，需要减去，然而 \(\operatorname{LCA}(u,v)\) 也在查询的树链内，因此还需将 \(\operatorname{LCA}(u,v)\) 的权值加上，从而得出结点 \(u\) 到结点 \(v\) 所经最短路径形成的序列的序列和为 \(f_u+f_v- 2f_{\operatorname{LCA}(u,v)}+a_{\operatorname{LCA}(u,v)}\)，其中 \(a\) 表示点权。
而 \(a_{\operatorname{LCA}(u,v)}\) 又可以由 \(f_{\operatorname{LCA}(u,v)}-f_{fa_{\operatorname{LCA}(u,v)}}\) 得出，其中 \(fa\) 表示该结点的父亲结点。因此也可以写作 \(f_u+f_v- f_{\operatorname{LCA}(u,v)}-f_{fa_{\operatorname{LCA}(u,v)}}\)，特殊的，如果 \(\operatorname{LCA}(u,v)\) 为根结点，那么查询的值就应为 \(f_u+f_v- f_{\operatorname{LCA}(u,v)}\)，因为根结点没有父亲结点。
这种做法需要求 LCA，因此单次查询的时间复杂度同样为 \(O(\log n)\)。
虽然这种思路很简单，代码也很好写，但是处理的问题必须满足可减，这就是它的局限性。面对复杂的静态树链问题，这种做法往往不会被采用。
参考代码如下：

1. #include<bits/stdc++.h>
2. using namespace std;
3. //#define int long long
4. #define I_love_Foccarus return
5. #define rep(i,a,b) for(int i=a;i<=b;i++)
6. #define deap(i,a,b) for(int i=a;i>=b;i--)
7. #define in(a) a=read()
8. #define fi first
9. #define se second
10. const int N = 1e5 + 5;
11. const int inf = INT_MAX;
12. inline int read() { //浓缩后的快读        
13.     int x=0,f=1,ch=getchar();
14.         while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
15.         while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
16.         I_love_Foccarus x*f;
17. }
18. struct Edge { //链式前向星存树
19.         int act , nex;
20. } edge[N];
21. int head[N] , eid;
22. void eadd(int u , int v) {
23.         edge[++eid].act = v , edge[eid].nex = head[u] , head[u] = eid;
24. }
25. int n , q;
26. int fa[N][21] , d[N] , f[N];
27. void dfs(int u,int dep) { //倍增 LCA 初始化
28.         d[u] = dep;
29.         for(int i = head[u] ; i ; i = edge[i].nex){
30.         int v = edge[i].act;
31.         f[v] += f[u]; //记录该结点到根结点的权值和
32.         dfs(v , dep + 1);       
33.         }        
34. }
35. int LCA(int x , int y) { //倍增 LCA
36.         if(d[x] < d[y])swap(x , y);
37.         for(int i = 20 ; i >= 0 ; i--) {
38.                 int v = fa[x][i];
39.                 if(d[v] < d[y])continue;
40.                 x = v;
41.         }
42.         if(x == y)return x;
43.         for(int i = 20 ; i >= 0 ; i--) {
44.                 if(fa[x][i] == fa[y][i])continue;
45.                 x = fa[x][i];
46.                 y = fa[y][i];
47.         }
48.         I_love_Foccarus fa[x][0];
49. }
50. signed main() {
51.         int root;
52.         in(n);
53.         rep(i , 1 , n)in(f[i]);
54.         rep(i , 1 , n) {
55.                 in(fa[i][0]);
56.                 if(fa[i][0] != i)eadd(fa[i][0] , i);
57.                 else root = i , fa[i][0] = 0; //让根结点指向权值为零的数
58.         }
59.         dfs(root , 1);
60.         for(int i = 1 ; i <= 20 ; i++) { //倍增 LCA 初始化
61.                 for(int j = 1 ; j <= n ; j++) {
62.                         int v = fa[j][i - 1];
63.                         fa[j][i] = fa[v][i - 1];
64.                 }
65.         }
66.         in(q);
67.         while(q--){
68.                 int u , v;
69.                 in(u) , in(v);
70.                 int lca = LCA(u , v);
71.                 printf("%d\n",f[u] + f[v] - f[lca] - f[fa[lca][0]]); //容斥原理求解
72.         }
73.         I_love_Foccarus 0;
74. }

复制代码

解法四：树上倍增

就像求倍增 LCA，在记录成倍增长的父结点信息的同时合并权值，然后在倍增求 LCA 的过程中将权值合并，也就是把查询的要合并的两条链拆解成若干个二进制片段，然后合并。信息不可重复，需要去重，为了权值避免权值重复合并，合并记录的信息不能计入成倍跳到了的结点的权值，然后在查询时加上漏掉的 LCA 的点权。
时间复杂度为 \(O(q\log n)\)。
参考代码如下：

1. #include<bits/stdc++.h>
2. using namespace std;
3. //#define int long long
4. #define I_love_Foccarus return
5. #define rep(i,a,b) for(int i=a;i<=b;i++)
6. #define deap(i,a,b) for(int i=a;i>=b;i--)
7. #define in(a) a=read()
8. #define fi first
9. #define se second
10. const int N = 1e5 + 5 , maxn = 1e6 + 5;
11. const int inf = INT_MAX;
12. inline int read() { //浓缩后的快读        
13.     int x=0,f=1,ch=getchar();
14.         while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
15.         while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
16.         I_love_Foccarus x*f;
17. }
18. struct Edge { //链式前向星存树
19.         int act , nex;
20. } edge[N];
21. int head[N] , eid;
22. void eadd(int u , int v) {
23.         edge[++eid].act = v , edge[eid].nex = head[u] , head[u] = eid;
24. }
25. vector< pair< pair<int , int> , int > >solve[maxn]; //LCA 标记
26. vector< pair<int , int> >Q[maxn]; //离线储存查询
27. int n , q , fa[N] , vis[N] , d[N] , a[N] , ans[maxn];
28. int find(int x) { //带权并查集合并
29.         if(fa[x] != fa[fa[x]]){ //如果父亲结点不是根结点
30.                 int root = find(fa[x]);
31.                 d[x] += d[fa[x]]; //将父亲结点权值合并到自身
32.                 fa[x] = root; //路径压缩
33.         }
34.         I_love_Foccarus fa[x];  
35. }
36. void Tarjan(int u) { //Tarjan 离线求树链和
37.         fa[u] = u , vis[u] = 1 , d[u] = a[u];  //结点初始化
38.         for(int i = head[u] ; i ; i = edge[i].nex) {
39.                 int v = edge[i].act;
40.                 Tarjan(v);
41.                 fa[v] = u; //可以直接合并
42.         }
43.         for(auto v:Q[u]){ //求 LCA 和打标记
44.         if(!vis[v.fi])continue;       
45.         solve[find(v.fi)].push_back(make_pair(make_pair(u , v.fi) , v.se));
46.         }
47.         for(auto v:solve[u]){ //处理每次询问
48.                 find(v.fi.fi) , find(v.fi.se); //进行权值合并
49.                 if(v.fi.fi == v.fi.se) ans[v.se] = a[u]; //分类讨论
50.                 else if(v.fi.fi == u || v.fi.se == u ) ans[v.se] = d[v.fi.fi] + d[v.fi.se];
51.                 else ans[v.se] = d[v.fi.fi] + d[v.fi.se] + a[u];
52.         }
53. }
54. signed main() {
55.         int root;
56.         in(n);
57.         rep(i , 1 , n)in(a[i]);
58.         rep(i , 1 , n) {
59.                 int f;
60.                 in(f);
61.                 if(f != i)eadd(f , i);
62.                 else root = i;
63.         }
64.         in(q);
65.         rep(i , 1 , q) { //离线记录每次询问
66.                 int u , v;
67.                 in(u) , in(v);
68.                 Q[u].push_back(make_pair(v , i));
69.                 Q[v].push_back(make_pair(u , i));
70.         }
71.         Tarjan(root); //Tarjan 离线求树链和
72.         rep(i , 1 , q) printf("%d\n",ans[i]);
73.         I_love_Foccarus 0;
74. }

复制代码

解法二：猫树分治

树链剖分的时间主要浪费在线段树的查询上，可以在这方面进行优化。由于查询的是一个静态区间，因此考虑用猫树分治实现，至于如何合并，可参考解法三。
由于树链剖分需要查询 \(O(\log n)\) 个子区间，因此猫树需要处理 \(O(q\log n)\) 次查询，如果采用朴素的猫树，时间复杂度为 \(O(q\log^2 n)\)，不能接受。猫树的一只 \(\log\) 主要消耗在确定 mid 上，可以在此方面进行优化。据说有一种二进制的方法可以直接实现，但是蒟蒻不会，因此用了 ST 表，维护区间内的一个数 \(x\)，满足以 \(x\) 为 mid 的最大区间长度，可以证明，查询的区间一定处于该区间的内部。该算法常数稍大，但把优化打满后勉强能过。
总时间复杂度为 \(O(q\log n)\)。
参考代码如下：

1. #include<bits/stdc++.h>
2. using namespace std;
3. //#define int long long
4. #define I_love_Foccarus return
5. #define rep(i,a,b) for(int i=a;i<=b;i++)
6. #define deap(i,a,b) for(int i=a;i>=b;i--)
7. #define in(a) a=read()
8. #define fi first
9. #define se second
10. const int N = 1e5 + 5;
11. const int inf = INT_MAX;
12. inline int read() { //浓缩后的快读        
13.     int x=0,f=1,ch=getchar();
14.         while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
15.         while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
16.         I_love_Foccarus x*f;
17. }
18. struct Edge { //链式前向星存树
19.         int act , nex;
20. } edge[N];
21. int head[N] , eid;
22. void eadd(int u , int v) {
23.         edge[++eid].act = v , edge[eid].nex = head[u] , head[u] = eid;
24. }
25. int n , q;
26. int fa[N][21] , f[N][21] , d[N] , vis[N] , a[N];
27. void dfs(int u,int dep) { //树上倍增初始化
28.         d[u] = dep;
29.         for(int i = head[u] ; i ; i = edge[i].nex){
30.         int v = edge[i].act;
31.         dfs(v , dep + 1);       
32.         }        
33. }   
34. int root;
35. int solve(int x , int y) { //树上倍增
36.     int ans = 0;
37.         if(d[x] < d[y])swap(x , y);
38.         for(int i = 20 ; i >= 0 ; i--) {
39.                 int v = fa[x][i];
40.                 if(d[v] < d[y])continue;  
41.         if(x != y)
42.                 ans += f[x][i];
43.                 x = v;
44.         }
45.         if(x == y) I_love_Foccarus ans + a[y];       
46.         for(int i = 20 ; i >= 0 ; i--) {
47.                 if(fa[x][i] == fa[y][i])continue;
48.                 ans += f[x][i] + f[y][i];
49.                 x = fa[x][i];
50.                 y = fa[y][i];
51.         }
52.         I_love_Foccarus ans + f[x][0] + f[y][0] + a[fa[x][0]];
53. }
54. signed main() {
55.         in(n);
56.         rep(i , 1 , n)in(a[i]);
57.         rep(i , 1 , n) {
58.                 in(fa[i][0]);
59.                 f[i][0] = a[i];
60.                 if(fa[i][0] != i)eadd(fa[i][0] , i);
61.                 else root = i;
62.         }
63.         dfs(root , 1);
64.         for(int i = 1 ; i <= 20 ; i++) { //树上倍增初始化
65.                 for(int j = 1 ; j <= n ; j++) {
66.                         int v = fa[j][i - 1];
67.                         if(fa[j][i - 1] == fa[v][i - 1])continue; //去重
68.                         fa[j][i] = fa[v][i - 1];
69.                         f[j][i] = f[j][i - 1] + f[v][i - 1]; //权值合并
70.                 }
71.         }
72.         in(q);
73.         while(q--){
74.                 int u , v;
75.                 in(u) , in(v);
76.                 printf("%d\n",solve(u , v));  
77.         }
78.         I_love_Foccarus 0;
79. }

复制代码

解法四：树上倍增

和例题一的思路一样，合并操作用加法重载后根本不用改，只需在返回值时分类讨论即可。时间复杂度一样。
参考代码如下：

[code]#includeusing namespace std;//#define int long long#define I_love_Foccarus return#define rep(i,a,b) for(int i=a;i=b;i--)#define in(a) a=read()#define fi first#define se secondconst int N = 1e5 + 5;const int inf = INT_MAX;inline int read() { //浓缩后的快读             int x=0,f=1,ch=getchar();        while(ch'9'){if (ch=='-') f=-1;ch=getchar();}        while(ch>='0'&&cha = this->b = this->c = this->d = x;        }        node friend operator + (const node &u , const node &v) { //重载加法处理合并                 node ans;                ans.a = max(max(u.a , v.a) , v.c + u.d);                ans.b = u.b + v.b;                ans.c = max(u.c , u.b + v.c);                ans.d = max(v.d , v.b + u.d);                I_love_Foccarus ans;        }}f[N][21]; struct Edge { //链式前向星存树         int act , nex;} edge[N];int head[N] , eid;inline void eadd(int u , int v) {        edge[++eid].act = v , edge[eid].nex = head , head = eid;}int n , q;int fa[N][21] , d[N] , vis[N] , a[N];void dfs(int u,int dep) { //树上倍增初始化         d = dep;        for(int i = head ; i ; i = edge.nex){        int v = edge.act;        dfs(v , dep + 1);                }         }   int root;           inline int c(int x){        return x > 0 ? x : 0;}int solve(int x , int y) { //树上倍增     node ansx = node(-0x3f3f3f3f) , ansy = node(-0x3f3f3f3f); //分别处理两个结点到 LCA 的链的信息         ansx.b = ansy.b = 0;        if(d[x] < d[y])swap(x , y);        for(int i = 20 ; i >= 0 ; i--) {                int v = fa[x];                if(d[v] < d[y])continue;          if(x != y)                ansx = ansx + f[x];                x = v;        }        if(x == y) I_love_Foccarus max(max(ansx.a , a[y]) , ansx.d + a[y]);                for(int i = 20 ; i >= 0 ; i--) {                if(fa[x] == fa[y])continue;                ansx = ansx + f[x];                ansy = ansy + f[y];                x = fa[x];                y = fa[y];        }        ansx = ansx + f[x][0];        ansy = ansy + f[y][0];        I_love_Foccarus max(max(ansx.a , ansy.a) , c(ansx.d) + c(ansy.d) + a[fa[x][0]]);  }signed main() {        in(n);        rep(i , 1 , n)in(a);        rep(i , 1 , n) {                in(fa[0]);                f[0] = node(a);                if(fa[0] != i)eadd(fa[0] , i);                else root = i;        }        dfs(root , 1);        for(int i = 1 ; i > 1;        if(q > 1 , tmp = tree[tree[idxu].cl].ans + tree[tree[idxv].cl].ans - tree[tree[lca].cl].ans - tree[tree[lca2].cl].ans; //容斥原理求解        if(q