点击刷新
树链剖分就是将树分割成多条链，然后利用数据结构（线段树、树状数组等）来维护这些链。
首先就是一些必须知道的概念：
- 重结点：子树结点数目最多的结点；
- 轻节点：父亲节点中除了重结点以外的结点；
- 重边：父亲结点和重结点连成的边；
- 轻边：父亲节点和轻节点连成的边；
- 重链：由多条重边连接而成的路径；
- 轻链：由多条轻边连接而成的路径；
比如上面这幅图中，用黑线连接的结点都是重结点，其余均是轻结点，2-11、1-11就是重链，其他就是轻链，用红点标记的就是该结点所在链的起点，也就是我们?提到的top结点，还有每条边的值其实是进行dfs时的执行序号。
算法中定义了以下的数组用来存储上边提到的概念：
| 名称 | 解释 |
|---|---|
| siz[u] | 保存以u为根的子树节点个数 |
| top[u] | 保存当前节点所在链的顶端节点 |
| son[u] | 保存重儿子 |
| dep[u] | 保存结点u的深度值 |
| faz[u] | 保存结点u的父亲节点 |
| tid[u] | 保存树中每个节点剖分以后的新编号（DFS的执行顺序） |
| rnk[u] | 保存当前节点在树中的位置 |
除此之外，还包括两种性质：
- 如果(u, v)是一条轻边，那么size(v) < size(u)/2；
- 从根结点到任意结点的路所经过的轻重链的个数必定都小与O(logn)；
首先定义以下数组：
1 const int MAXN = (100000 << 2) + 10; 2 3 //Heavy-light Decomposition STARTS FORM HERE 4 int siz[MAXN];//number of son 5 int top[MAXN];//top of the heavy link 6 int son[MAXN];//heavy son of the node 7 int dep[MAXN];//depth of the node 8 int faz[MAXN];//father of the node 9 int tid[MAXN];//ID -> DFSID 10 int rnk[MAXN];//DFSID -> ID
算法大致需要进行两次的DFS，第一次DFS可以得到当前节点的父亲结点（faz数组）、当前结点的深度值（dep数组）、当前结点的子结点数量（size数组）、当前结点的重结点（son数组）
1 void dfs1(int u, int father, int depth) { 2 /* 3 * u: 当前结点 4 * father: 父亲结点 5 * depth: 深度 6 */ 7 // 更新dep、faz、siz数组 8 dep[u] = depth; 9 faz[u] = father; 10 siz[u] = 1; 11 12 // 遍历所有和当前结点连接的结点 13 for (int i = head[u]; i; i = edg[i].next) { 14 int v = edg[i].to; 15 // 如果连接的结点是当前结点的父亲结点，则不处理 16 if (v != faz[u]) { 17 dfs1(v, u, depth + 1); 18 // 收敛的时候将当前结点的siz加上子结点的siz 19 siz[u] += siz[v]; 20 // 如果没有设置过重结点son或者子结点v的siz大于之前记录的重结点son，则进行更新 21 if (son[u] == -1 || siz[v] > siz[son[u]]) { 22 son[u] = v; 23 } 24 } 25 } 26 }
第二次DFS的时候则可以将各个重结点连接成重链，轻节点连接成轻链，并且将重链（其实就是一段区间）用数据结构（一般是树状数组或线段树）
来进行维护，并且为每个节点进行编号，其实就是DFS在执行时的顺序（tid数组），以及当前节点所在链的起点（top数组），还有当前节点在树中
的位置（rank数组）
1 void dfs2(int u, int t) { 2 /** 3 * u：当前结点 4 * t：起始的重结点 5 */ 6 top[u] = t; // 设置当前结点的起点为t 7 tid[u] = cnt; // 设置当前结点的dfs执行序号 8 rnk[cnt] = u; // 设置dfs序号对应成当前结点 9 cnt++; 10 11 // 如果当前结点没有处在重链上，则不处理 12 if (son[u] == -1) { 13 return; 14 } 15 // 将这条重链上的所有的结点都设置成起始的重结点 16 dfs2(son[u], t); 17 // 遍历所有和当前结点连接的结点 18 for (int i = head[u]; i; i = edg[i].next) { 19 int v = edg[i].to; 20 // 如果连接结点不是当前结点的重子结点并且也不是u的父亲结点，则将其的top设置成自己，进一步递归 21 if (v != son[u] && v != faz[u]){ 22 dfs2(v, v); 23 } 24 } 25 }
而修改和查询操作原理是类似的，以查询操作为例，其实就是个LCA，不过这里使用了top来进行加速，因为top可以直接跳转到该重链的起始结点，
轻链没有起始结点之说，他们的top就是自己。需要注意的是，每次循环只能跳一次，并且让结点深的那个来跳到top的位置，避免两个一起跳从而插肩而过。
树链剖分模板：
1 //树链剖分 2 //query() update()数据结构的操作 3 #include<bits/stdc++.h> 4 using namespace std; 5 #define mem(a,b) memset(a,b,sizeof a) 6 #define mp make_pair 7 #define eps 1e-8 8 typedef long long ll; 9 typedef unsigned long long ull; 10 const int INF=0x3f3f3f3f; 11 const ll inf=0x3f3f3f3f3f3f3f3fll; 12 const int maxn=(100000<<2)+10; 13 int siz[maxn],top[maxn],son[maxn],dep[maxn]; 14 int fa[maxn],tid[maxn],rnk[maxn],cnt; 15 int head[maxn],tot; 16 17 struct Node{ 18 int to,nxt; 19 } edg[maxn<<2]; 20 21 void addedge(int u,int v) 22 { 23 edg[tot].to=v; 24 edg[tot].nxt=head[u]; 25 head[u]=tot++; 26 } 27 28 void dfs1(int u,int father,int depth) //处理出每个点的深度，重儿子，父亲节点以及以它为根的子节点的数量 29 { 30 dep[u]=depth; 31 fa[u]=father; 32 siz[u]=1; 33 for(int i=head[u];i;i=edg[i].nxt) 34 { 35 int v=edg[i].to; 36 if(v!=fa[u]) 37 { 38 dfs1(v,u,depth+1); 39 siz[u]+=siz[v]; 40 if(son[u]==-1||siz[v]>siz[son[u]]) son[u]=v; 41 } 42 } 43 } 44 45 void dfs2(int u, int t) //getpos() 46 { 47 top[u]=t; 48 tid[u]=cnt; rnk[cnt]=u; //用于数据结构中位置的还原 49 cnt++; 50 if(son[u]==-1) return; 51 dfs2(son[u],t); 52 for(int i=head[u];i;i=edg[i].nxt) 53 { 54 int v=edg[i].to; 55 if(v!=son[u] && v!=fa[u]) dfs2(v,v); 56 } 57 } 58 59 int query_path(int x, int y) //查询结点x到结点y的路径和 60 { 61 int ans=0; 62 int fx=top[x],fy=top[y]; 63 while(fx!=fy) 64 { 65 if(dep[fx]>=dep[fy]) ans+=query(1,tid[fx],tid[x]),x=fa[fx]; 66 else ans+=query(1,tid[fy],tid[y]),y=fa[fy]; 67 fx=top[x],fy=top[y]; 68 } 69 if(x!=y) 70 { 71 if(tid[x]<tid[y]) ans+=query(1,tid[x],tid[y]); 72 else ans+=query(1,tid[y],tid[x]); 73 } 74 else ans+=query(1,tid[x],tid[y]); 75 return ans; 76 } 77 78 void update_path(int x,int y,int z) //更新结点x到结点y的值 +z 79 { 80 int fx=top[x],fy=top[y]; 81 while(fx!=fy) 82 { 83 if(dep[fx]>dep[fy]) update(1,tid[fx],tid[x],z),x=fa[fx]; 84 else update(1,tid[fy],tid[y],z),y=fa[fy]; 85 fx=top[x],fy=top[y]; 86 } 87 if(x!=y) 88 { 89 if(tid[x]<tid[y]) update(1,tid[x],tid[y],z); 90 else update(1,tid[y],tid[x],z); 91 } 92 else update(1,tid[x],tid[y],z); 93 }
