参考博客树链剖分原理和实现
树链剖分笔记

树链剖分

树剖是通过轻重边剖分将树分割成多条链，然后利用数据结构来维护这些链（本质上是一种优化暴力）

首先就是一些必须知道的概念：
重节点：子树结点数目最多的结点；
轻节点：父亲节点中除了重结点以外的结点；
重边：父亲结点和重结点连成的边；
轻边：父亲节点和轻节点连成的边；
重链：由多条重边连接而成的路径；
轻链：由多条轻边连接而成的路径；

下面讲讲树链剖分的算法

一般情况下树链剖分都需要进行两次DFS，第一次得到每个节点的子树大小和每个节点的深度，每个节点的父节点和每个节点的重节点。
siz[u]：u子树大小
d[u]：u节点的深度
fa[u]：u节点的父节点
son[u]：u的重节点

DFS(int u,int fa)
{siz[u] = 1;d[u] = d[fa]+1;fa[u] = fa;son[u] = 0;for(int i = head[u];~i;i=E[i].next){int v = E[i].to;if(v==fa) continue;DFS(v,u);siz[u] += siz[v];if(siz[son[u]]<siz[v]) son[u]=v;}
}
dfs1(1,0);

第二次DFS的时候可以将各个重结点连接成重链，轻节点连接成轻链，并且将重链（其实就是一段区间）用数据结构（一般是树状数组或线段树）来进行维护，并且为每个节点进行编号，其实就是DFS在执行时的顺序（tid数组），以及当前节点所在链的起点（top数组），还有DFS序数组（rank数组）。

 
void dfs2(int u, int t) {/*** u：当前结点* t：起始的重结点*/top[u] = t;    // 设置当前结点的起点为ttid[u] = cnt;  // 设置当前结点的dfs序号rnk[cnt] = u;  // 设置dfs序号对应成当前结点cnt++;
​// 如果当前节点没有没有重节点，则不处理if (son[u] == 0) {return;}// 将这条重链上的所有的结点都设置成起始的重结点dfs2(son[u], t);// 遍历所有和当前节点连接的节点for (int i = head[u]; i; i = E[i].next) {int v = E[i].to;// 如果连接结点不是当前结点的重子结点并且也不是u的父亲结点，则将其的top设置成自己，进一步递归if (v != son[u] && v != fa[u]){dfs2(v, v);}}
}
dfs2(1,1);

用线段树维护重链

前面已经用tid数组记录了每个节点的DFS序号，因此只需要用线段树维护tid数组即可。具体操作见下代码：

ll query_path(int x, int y) {/*** x：结点x* y：结点y* 查询结点x到结点y的路径和*/ll ans = 0;int fx = top[x], fy = top[y];// 直到x和y两个结点所在链的起始结点相等才表明找到了LCAwhile (fx != fy) {if (dep[fx] >= dep[fy]) {// 已经计算了从x到其链中起始结点的路径和//query就是线段树的查询函数ans += query(1,n, tid[fx], tid[x],1);// 将x设置成起始结点的父亲结点，走轻边，继续循环x = faz[fx];} else {ans += query(1,n, tid[fy], tid[y],1);y = faz[fy];}fx = top[x], fy = top[y];}// 即便找到了LCA，但是前面也只是分别计算了从一开始到最终停止的位置和路径和// 如果两个结点不一样，表明仍然需要计算两个结点到LCA的路径和if (x != y) {if (tid[x] < tid[y]) {ans += query(1, n, tid[x], tid[y], 1);} else {ans += query(1, n, tid[y], tid[x], 1);}} else ans += query(1, n, tid[x], tid[y], 1);return ans;
}
​
void update_path(int x, int y, int z) {/*** x：结点x* y：结点y* z：需要加上的值* 更新结点x到结点y的值*/int fx = top[x], fy = top[y];while(fx != fy) {if (dep[fx] > dep[fy]) {update(1, n, z, tid[fx],tid[x], 1);x = faz[fx];} else {update(1, n, z, tid[fx],tid[x], 1);y = faz[fy];}fx = top[x], fy = top[y];}if (x != y)if (tid[x] < tid[y]) update(1, n, z, tid[fx],tid[x], 1);else update(1, n, z, tid[fx],tid[x], 1);else update(1, n, z, tid[fx],tid[x], 1);
}