重链剖分

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);
}