重链剖分
<p><img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/edf804cd7e679f9d3627ee67473ffbe0" alt="" />
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/da21ebe0f39ac5e853140406db166e92" alt="" /></p>
<pre><code class="language-cpp">const int maxn=1e5+10;
struct Edge{
int next;
int to;
};
Edge edge[maxn << 1];
int rt, n, m, r, cnt;
int num[maxn], head[maxn], f[maxn], d[maxn], size[maxn];
int son[maxn], rk[maxn], top[maxn], id[maxn];
void dfs1(int u, int fa, int depth){ //当前节点、父节点、层次深度
f[u] = fa;
d[u] = depth;
size[u] = 1; //这个点本身size=1
for(int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
if(v == fa) continue;
dfs1(v, u, depth + 1); //层次深度+1
size[u] += size[v]; //子节点的size已被处理，用它来更新父节点的size
if(size[v] > size[son[u]]) son[u] = v; //选取size最大的作为重儿子
}
}
void dfs2(int u, int t){ //当前节点、重链顶端
top[u] = t;
id[u] = ++cnt; //标记dfs序
rk[cnt] = u; //序号cnt对应节点u
if(!son[u]) return;
dfs2(son[u], t);
/*我们选择优先进入重儿子来保证一条重链上各个节点dfs序连续，
一个点和它的重儿子处于同一条重链，所以重儿子所在重链的顶端还是t*/
for(int i = head[u]; ~i; i = edge[i].next){
int v = edge[i].to;
//一个点位于轻链底端，那么它的top必然是它本身
if(v != son[u] && v != f[u]) dfs2(v,v);
}
}
int sum(int x,int y){//x到y路径和
int ret = 0;
while(top[x] != top[y]){
if(d[top[x]] < d[top[y]]) swap(x, y);
(ret += query(id[top[x]], id[x], rt)) %= mod;
x = f[top[x]];
}
if(id[x] > id[y]) swap(x,y);
return (ret + query(id[x], id[y], rt)) % mod;
}
void build(int l,int r,int x)//这个函数主要看构造树，num[rk[l]]
{
if(l==r)
{
a[x].sum=v[rk[l]],a[x].l=a[x].r=l;
return;
}
int mid=l+r>>1;
a[x].ls=cnt++,a[x].rs=cnt++;
build(l,mid,a[x].ls),build(mid+1,r,a[x].rs);
a[x].l=a[a[x].ls].l,a[x].r=a[a[x].rs].r;
pushup(x);
}
//进入
int main(){
memset(head, -1, sizeof(head));
dfs1(root,0,1);//root
dfs1(root,root);
}
</code></pre>