這幾天學了一個樹鍊剖分，覺得還不是很難，這裡我試着講一講吧。
首先，我認為樹鍊剖分是把在樹上一個節點一個節點的走改為按照某種規則跳，進而降低了時間複雜度。
那這是什麼規則呢？
首先我們得知道什麼是重鍊，知道什麼是重鍊就得先知道什麼是重兒子，重兒子就是子樹較大的兒子。然後對于一個點，我們總是往他的重兒子走，這樣就構成了重鍊，那麼剩下的就是輕鍊。
放張圖直覺些
然後我們同樣可以對樹進行dfs，隻不過重兒子優先，這樣我們也得到了一個dfs序，于是我們把樹上問題成功轉化成了線性問題。接着就可以用線段樹等資料結構維護了。
那就拿這道闆子體為例：https://www.luogu.org/problemnew/show/P3384
首先是兩遍dfs，第一遍dfs維護子樹大小size[]，節點深度dep[]，重兒子son[]，以及一個節點的父親節點（因為如果跳到了一條鍊的頂端，就要再自己走到他的父親節點）。
1 void dfs1(int now) 2 { 3 vis[now] = 1; 4 size[now] = 1; 5 for(int i = 0; i < (int)v[now].size(); ++i) 6 { 7 if(!vis[v[now][i]]) 8 { 9 dep[v[now][i]] = dep[now] + 1;10 fa[v[now][i]] = now;11 dfs1(v[now][i]);12 size[now] += size[v[now][i]];13 if(!son[now] || size[son[now]] < size[v[now][i]]) son[now] = v[now][i];14 //如果沒有重兒子，或者目前子樹大小大于重兒子的子樹大小，就更新重兒子 15 }16 }17 } 第二遍dfs是維護dfs序dfsx[]，每一條鍊的頂端是哪一個節點。但我們還要在維護一個pos[]，因為當我們将樹轉化成線性後，用線段樹建樹的時候需要添加節點，而這個節點的編号是dfs序的編号，是以需要再用一個數組記錄dfs序的編号所對應的樹上節點編号。
1 int cnt = 0, dfsx[maxn], pos[maxn], top[maxn]; 2 void dfs2(int now) 3 { 4 //dfsx[]因為智慧更新一次，是以可以當做vis[]用 5 dfsx[now] = ++cnt; pos[cnt] = now; 6 if(son[now]) 7 { 8 top[son[now]] = top[now]; 9 dfs2(son[now]); //優先走重兒子，保證一條鍊在dfs序上的編号是連續的 10 }11 for(int i = 0; i < (int)v[now].size(); ++i)12 {13 if(!dfsx[v[now][i]] && son[now] != v[now][i]) //再走不是重兒子的節點 14 {15 top[v[now][i]] = v[now][i]; //輕兒子所在的鍊隻有他自己一個節點，是以頂端節點就是他自己 16 dfs2(v[now][i]);17 }18 }19 } 這兩個預處理完事後就可以看看題了。
第一個詢問，将樹從x到y結點最短路徑上所有節點的值都加上z。
首先我們要将x，y移到同一條鍊上，具體操作就是如果其中一個點所在鍊的頂端的深度更低，就将他跳到鍊的頂端，并更新他到頂端節點的區間。
移到同一條鍊上後，就更新這兩個點的區間就行了
1 void pathUpdate(int x, int y, int z) 2 { 3 while(top[x] != top[y]) //先把這倆搞到一條鍊上 4 { 5 if(dep[top[x]] < dep[top[y]]) swap(x, y); //預設讓x跳 6 update(dfsx[top[x]], dfsx[x], 1, z); 7 x = fa[top[x]]; 8 } 9 if(dfsx[x] > dfsx[y]) swap(x, y);10 update(dfsx[x], dfsx[y], 1, z);11 } 操作2： 求樹從x到y結點最短路徑上所有節點的值之和
和修改一樣，先把兩點移到同一條鍊上，然後計算跳的點在該鍊上的貢獻
1 ll pathQuery(int x, int y) 2 { 3 ll ret = 0; 4 while(top[x] != top[y]) 5 { 6 if(dep[top[x]] < dep[top[y]]) swap(x, y); 7 ret += query(dfsx[top[x]], dfsx[x], 1); ret %= mod; 8 x = fa[top[x]]; 9 }10 if(dfsx[x] > dfsx[y]) swap(x, y);11 ret += query(dfsx[x], dfsx[y], 1); ret %= mod;12 return ret;13 } 操作3： 将以x為根節點的子樹内所有節點值都加上z
值得一提的是，盡管我們在維護dfs序時是重鍊優先周遊，但仍滿足一個節點以及他的子樹在dfs序上是一段長為子樹大小的連續區間，自己畫一畫就明白了
這裡和查詢放一塊
1 void sbtUpdate(int x, int z)2 {3 update(dfsx[x], dfsx[x] + size[x] - 1, 1, z);4 }5 ll sbtQuery(int x)6 {7 return query(dfsx[x], dfsx[x] + size[x] - 1, 1);8 } 1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 #define enter printf("\n") 10 #define space printf(" ") 11 typedef long long ll; 12 const int INF = 0x3f3f3f3f; 13 const int maxn = 1e5 + 5; 14 inline ll read() 15 { 16 ll ans = 0; 17 char ch = getchar(), last = ' '; 18 while(!isdigit(ch)) {last = ch; ch = getchar();} 19 while(isdigit(ch)) 20 { 21 ans = ans * 10 + ch - '0'; ch = getchar();
22 } 23 if(last == '-') ans = -ans; 24 return ans; 25 } 26 inline void write(ll x) 27 { 28 if(x < 0) x = -x, putchar('-'); 29 if(x >= 10) write(x / 10); 30 putchar('0' + x % 10); 31 } 32 33 int n, m, s, mod; 34 int a[maxn]; 35 vector<int> v[maxn]; 36 37 bool vis[maxn]; 38 int fa[maxn], son[maxn], size[maxn], dep[maxn]; 39 void dfs1(int now) 40 { 41 vis[now] = 1; 42 size[now] = 1; 43 for(int i = 0; i < (int)v[now].size(); ++i) 44 { 45 if(!vis[v[now][i]]) 46 { 47 dep[v[now][i]] = dep[now] + 1; 48 fa[v[now][i]] = now; 49 dfs1(v[now][i]); 50 size[now] += size[v[now][i]]; 51 if(!son[now] || size[son[now]] < size[v[now][i]]) son[now] = v[now][i]; 52 //如果沒有重兒子，或者目前子樹大小大于重兒子的子樹大小，就更新重兒子 53 } 54 } 55 } 56 //第二遍dfs是維護dfs序dfsx[]，每一條鍊的頂端是哪一個節點 57 58 int cnt = 0, dfsx[maxn], pos[maxn], top[maxn]; 59 void dfs2(int now) 60 { 61 //dfsx[]因為智慧更新一次，是以可以當做vis[]用 62 dfsx[now] = ++cnt; pos[cnt] = now; 63 if(son[now]) 64 { 65 top[son[now]] = top[now]; 66 dfs2(son[now]); //優先走重兒子，保證一條鍊在dfs序上的編号是連續的 67 } 68 for(int i = 0; i < (int)v[now].size(); ++i) 69 { 70 if(!dfsx[v[now][i]] && son[now] != v[now][i]) //再走不是重兒子的節點 71 { 72 top[v[now][i]] = v[now][i]; //輕兒子所在的鍊隻有他自己一個節點，是以頂端節點就是他自己 73 dfs2(v[now][i]); 74 } 75 } 76 } 77 78 int l[maxn << 2], r[maxn << 2]; 79 ll sum[maxn << 2], lazy[maxn << 2]; 80 void build(int L, int R, int now) 81 { 82 l[now] = L; r[now] = R; 83 if(L == R) {sum[now] = a[pos[L]]; return;} 84 int mid = (L + R) >> 1; 85 build(L, mid, now << 1); 86 build(mid + 1, R, now << 1 | 1); 87 sum[now] = (sum[now << 1] + sum[now << 1 | 1]) % mod;
88 } 89 void pushdown(int now) 90 { 91 if(lazy[now]) 92 { 93 lazy[now << 1] += lazy[now]; lazy[now << 1] %= mod; 94 lazy[now << 1 | 1] += lazy[now]; lazy[now << 1 | 1] %= mod; 95 sum[now << 1] += (ll)(r[now << 1] - l[now << 1] + 1) * lazy[now]; sum[now << 1] %= mod; 96 sum[now << 1 | 1] += (ll)(r[now << 1 | 1] - l[now << 1 | 1] + 1) * lazy[now]; sum[now << 1 | 1] %= mod; 97 lazy[now] = 0; 98 } 99 }100 void update(int L, int R, int now, int d)101 {102 if(L == l[now] && R == r[now])103 {104 sum[now] += (ll)(r[now] - l[now] + 1) * d; sum[now] %= mod;105 lazy[now] += d; lazy[now] %= mod;106 return;107 }108 pushdown(now);109 int mid = (l[now] + r[now]) >> 1;110 if(R <= mid) update(L, R, now << 1, d);111 else if(L > mid) update(L, R, now << 1 | 1, d);112 else {update(L, mid, now << 1, d); update(mid + 1, R, now << 1 | 1, d);}113 sum[now] = sum[now << 1] + sum[now << 1 | 1];114 }115 ll query(int L, int R, int now)116 {117 if(L == l[now] && R == r[now]) return sum[now];118 pushdown(now);119 int mid = (l[now] + r[now]) >> 1;120 if(R <= mid) return query(L, R, now << 1);121 else if(L > mid) return query(L, R, now << 1 | 1);122 else return (query(L, mid, now << 1) + query(mid + 1, R, now << 1 | 1)) % mod;123 }124 125 void pathUpdate(int x, int y, int z)126 {127 while(top[x] != top[y]) //先把這倆搞到一條鍊上 128 {129 if(dep[top[x]] < dep[top[y]]) swap(x, y); //預設讓x跳 130 update(dfsx[top[x]], dfsx[x], 1, z);131 x = fa[top[x]];132 }133 if(dfsx[x] > dfsx[y]) swap(x, y);134 update(dfsx[x], dfsx[y], 1, z);135 }136 ll pathQuery(int x, int y)137 {138 ll ret = 0;139 while(top[x] != top[y])140 {141 if(dep[top[x]] < dep[top[y]]) swap(x, y);142 ret += query(dfsx[top[x]], dfsx[x], 1); ret %= mod;143 x = fa[top[x]];144 }145 if(dfsx[x] > dfsx[y]) swap(x, y);146 ret += query(dfsx[x], dfsx[y], 1); ret %= mod;147 return ret;148 }149 150 void sbtUpdate(int x, int z)151 {152 update(dfsx[x], dfsx[x] + size[x] - 1, 1, z);153 }154 ll sbtQuery(int x)155 {156 return query(dfsx[x], dfsx[x] + size[x] - 1, 1);157 }158 159 int main()160 {161 n = read(); m = read(); s = read(); mod = read();162 for(int i = 1; i <= n; ++i) a[i] = read();163 for(int i = 1 ; i < n; ++i)164 {165 int a = read(), b = read();166 v[a].push_back(b); v[b].push_back(a);167 }168 dfs1(s);
169 top[s] = s; dfs2(s);
170 build(1, n, 1);171 for(int i = 1; i <= m ; ++i)172 {173 int d = read();174 if(d == 1)
175 {176 int x = read(), y = read(), z = read();177 pathUpdate(x, y, z);178 }179 else if(d == 2)180 {181 int x = read(), y = read();182 write(pathQuery(x, y)); enter;183 }184 else if(d == 3)185 {186 int x = read(), z = read();187 sbtUpdate(x, z);188 }189 else190 {191 int x = read();192 write(sbtQuery(x)); enter;193 }194 }195 return 0;196 } ![C++入門指南及實戰 第一步 概述及經典HelloWorld[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)