## 树链剖分 ### 问题引入 > 树链剖分（树剖）：将树分解为一条条不相交的，从祖先到孙子的链。 > > 基本概念 ： > > - 轻儿子：除了重儿子的所有儿子 > - **重儿子：节点的的最大子节点** > - 轻边，重边：与轻儿子和重儿子相连的边 > - 轻链，重链：均由重（轻）儿子构成的链 > >  ### 算法解析 **构建如图所示的树链结构之后，根据轻重链的特性，可以优化LCA过程** #### 树剖LCA代码 ```c++ const int N = 6e5 + 9; const int INF = 0x3f3f3f3f; const int M = 1e9 + 9; vector<int> node[N]; int depth[N],son[N], fa[N],sIze[N]; // son数组存每一个节点唯一的重儿子节点，通过sIze数组（子树大小）更新 int topx[N];// 轻重链的链头节点 void dfs_init(int k,int f) { depth[k] = depth[f] + 1; fa[k] = f; sIze[k] = 1; for(int i = 0;i < node[k].size(); i++) { int v = node[k][i]; if(v != f) { dfs_init(v,k); sIze[k] += sIze[v]; if(sIze[son[k]] < sIze[v]) son[k] = v; // 更新重儿子节点 } } } void dfs_Top(int k,int f) { topx[k] = f; if(son[k]) dfs_Top(son[k],f); else return ; for(int i = 0;i < node[k].size(); i++) { int v = node[k][i]; if(v != fa[k] && v != son[k]) dfs_Top(v , v); } } //以上都是对树结构的初始化，不仅针对LCA int LCA(int a ,int b) { while(topx[a] != topx[b]) { if(depth[topx[a]] < depth[topx[b]]) swap(a , b); a = fa[topx[a]]; } // 观察 上述子链的构成情况，先重链后轻链，各个链头也是重儿子（根节点也是重儿子） // 然后 轻链头结点是重链头节点的子节点，所以要去找 子链的父节点 return depth[a] < depth[b] ? a : b; } void solve() { int n, m ,s; cin >> n >>m >> s; for(int i = 1;i <= n - 1; i ++) { int l ,r ; cin>> l>> r; node[l].push_back(r); node[r].push_back(l); } dfs_init(s,0)， dfs_Top(s,s); for(int i = 1;i <= m;i++) { int l ,r; cin >>l >> r; cout<<LCA(l ,r) << endl; } return; } ``` #### 树剖———线段树优化树上操作 ##### 线段树优化代码 ```c++ const int N = 1e5 + 9; const int INF = 0x3f3f3f3f; const int M = 1e9 + 9; int mod = 0; vector<int> node[N]; int depth[N],son[N], fa[N],sIze[N]; int topx[N]; int nid[N], w[N], nw[N]; // 树节点对应线段树结点的翻译数组， 树节点权值，线段树结点权值 struct Node{ int l, r; ll sum, tag; }segment[N << 2]; int cnt = 0; ///////////////////////////////////////////////////////////////////// void dfs_init(int k,int f) { depth[k] = depth[f] + 1; fa[k] = f; sIze[k] = 1; for(int i = 0;i < node[k].size(); i++) { int v = node[k][i]; if(v != f) { dfs_init(v,k); sIze[k] += sIze[v]; if(sIze[son[k]] < sIze[v]) son[k] = v; } } } void dfs_Top(int k,int f) { nid[k] = ++cnt, nw[cnt] = w[k]; topx[k] = f; if(son[k]) dfs_Top(son[k],f); else return ; for(int i = 0;i < node[k].size(); i++) { int v = node[k][i]; if(v != fa[k] && v != son[k]) dfs_Top(v , v); } } /////////////////////////////////预处理节点基本信息//////////////////////////////////// ///////////////////////////////////////////////////////////////////////////////////// void pushdown (int k) { segment[k << 1].sum += (segment[k << 1].r - segment[k << 1].l + 1) * segment[k].tag; segment[k << 1 | 1].sum += (segment[k << 1 | 1].r - segment[k << 1 | 1].l + 1 ) * segment[k].tag; segment[k << 1].tag += segment[k].tag; segment[k << 1 | 1].tag += segment[k].tag; segment[k << 1].sum %= mod,segment[k << 1 | 1].sum %= mod; segment[k].tag = 0; return ; } void build(int k, int l, int r) { segment[k].l = l, segment[k].r = r; if(l == r) { segment[k].sum = nw[l]; return ; } ll mid = l + r >> 1; build(k << 1 , l, mid); build(k << 1 | 1, mid + 1 , r); segment[k].sum = segment[k << 1].sum + segment[k << 1 | 1].sum; } void updata(int k ,int qx,int qy, int x) { if(qx <= segment[k].l && segment[k].r <= qy) { segment[k].sum += (segment[k].r - segment[k].l + 1) * x; segment[k].tag += x; return ; } if(qx > segment[k].r || qy < segment[k].l) return ; pushdown(k); updata(k << 1 , qx, qy, x); updata(k << 1 | 1, qx ,qy , x); segment[k].sum = segment[k << 1].sum + segment[k << 1 | 1].sum; return ; } ll query(int k, int qx,int qy) { if(qx <= segment[k].l && segment[k].r <= qy) { return segment[k].sum % mod; } if(qx > segment[k].r || qy < segment[k].l) return 0; pushdown(k); return (query(k << 1 , qx, qy) + query(k << 1 | 1, qx ,qy)) % mod; } //////////////////////////线段树部分（维护树剖区间）//////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////// void updata_LCA(int a ,int b,int x) { while(topx[a] != topx[b]) { if(depth[topx[a]] < depth[topx[b]]) swap(a , b); updata(1,nid[topx[a]],nid[a],x); a = fa[topx[a]]; } if(depth[a] > depth[b]) swap(a , b); updata(1,nid[a],nid[b],x); return ; } ll query_LCA(int a, int b) { ll ans = 0; while(topx[a] != topx[b]) { if(depth[topx[a]] < depth[topx[b]]) swap(a , b); ans += query(1,nid[topx[a]],nid[a]); ans %= mod; a = fa[topx[a]]; } if(depth[a] > depth[b]) swap(a , b); ans=(ans+query(1, nid[a], nid[b]))%mod; return ans % mod; } /////////////////////////////////树剖路径部分/////////////////////////////////////////// void solve() { int n, m ,s, p; cin >> n >>m >> s >> p; mod = p; for(int i = 1;i <= n;i ++) cin >> w[i]; for(int i = 1;i <= n - 1; i ++) { int l ,r ; cin>> l>> r; node[l].push_back(r); node[r].push_back(l); } dfs_init(s,0); dfs_Top(s,s); build(1 ,1 ,cnt); for(int i = 1;i <= m; i ++) { int op ; cin >> op; int l, r, k; if(op == 1) { cin>> l >> r >> k; updata_LCA(l, r, k); } else if(op == 2) { cin >> l >> r; cout<< query_LCA(l, r) << endl; } else if(op == 3) { cin>> l >> k; updata(1 , nid[l], nid[l] + sIze[l] - 1, k); } else{ cin >> k; cout << query(1 , nid[k], nid[k] + sIze[k] - 1) <<endl; } } return; } ``` ------ ------