树链剖分

实现树上的相关修改，查询操作的算法思路
将树上的相关操作简化成多条链，可以用数据结构来维护相关的链
时间复杂度主要在数据结构维护中

如何将树上的点有规律地拆分成链
定义:
重儿子：在父亲节点的所有儿子中子树节点数目最多的点（只能有一个点）
ps:当有两个及以上的点满足条件时，主要看程序遍历的方式与顺序
轻儿子：父亲节点中出了重儿子之外的点
规定将每个链头定义为其父亲节点的轻节点或根节点
重边：父亲节点连接重儿子的边
轻边：父亲节点连接轻儿子的边
重链：多条重链而构成的路径
轻链：多条轻链而构成的路径

dfs1

找到所有点的重儿子

int son[N];
int size[N];
int deep[N];
int fa[N];
void dfs1(int x){
	size[x]=1;
	deep[x]=deep[fa[x]]+1;
	int k=head[x];
	while(k!=0){
		if(e[k].to!=fa[x]){
			fa[e[k].to]=x;
			dfs1(e[k].to);
			size[x]+=size[e[k].to];
			if(size[son[x]]<size[e[k].to]){
				son[x]=e[k].to;
			}
		}
		k=e[k].next;
	}
}

dfs2

优先遍历所有的重儿子，重组节点编号
在重组的节点编号上维护链

int ant;
int id[N];
int top[N];
int rank[N];
void dfs2(int x,int t){
	top[x]=t;
	id[x]=++ant;
	rank[ant]=x;
	if(!son[x]){ return ;}
	dfs2(son[x],t);
	int k=head[x];
	while(k!=0){
		if(e[k].to!=fa[x]&&e[k].to!=son[x]){
			dfs2(e[k].to,e[k].to);
		}
		k=e[k].next;
	}
}

线段树建图

void build(int id,int l,int r){
    if(l==r){
        seg[id]=ai[rk[l]];
        return ;
    }
    int mid=(l+r)>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    push_up(id);
}

查找$lca$

将线段树上两点之间路径进行修改
时间复杂度: $nlogn$

void ask1(int x,int y,int v){
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        qu_add(id[top[x]],id[x],1,1,n,v);
        x=fa[top[x]];
    }
    if(id[x]>id[y]) swap(x,y);
    qu_add(id[x],id[y],1,1,n,v);
}

统计树上两点之间的信息之和
以求和为例

int ask2(int x,int y){
    int sum=0;
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        sum=(sum+query(id[top[x]],id[x],1,1,n))%p;
        x=fa[top[x]];
    }
    if(id[x]>id[y]) swap(x,y);
    sum=(sum+query(id[x],id[y],1,1,n))%p;
    return sum;
}

模版题

P3384 【模板】轻重链剖分

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(register int i=(a); i<=(b); ++i)
#define per(i,a,b) for(register int i=(a); i>=(b); --i)
#define ll long long
#define N 100010
using namespace std;
int n,m,r,p;
int ai[N];
struct node{
    int to;
    int next;
}e[2*N];
int arr;
int head[N];
void add(int u,int v){
    e[++arr].next=head[u];
    e[arr].to=v;
    head[u]=arr;
}
int son[N];
int size[N];
int deep[N];
int fa[N];
void dfs1(int x){
    deep[x]=deep[fa[x]]+1;
    size[x]=1;
    for(int k=head[x]; k; k=e[k].next){
        int v=e[k].to;
        if(v!=fa[x]){
            fa[v]=x;
            dfs1(v);
            size[x]+=size[v];
            if(size[son[x]]<size[v]) son[x]=v;
        }
    }
}
int top[N];
int id[N];
int rk[N];
int ant;
void dfs2(int x,int t){
    top[x]=t;
    id[x]=++ant;
    rk[ant]=x;
    if(!son[x]) return ;
    dfs2(son[x],t); 
    for(int k=head[x]; k; k=e[k].next){
        int v=e[k].to;
        if(v!=fa[x]&&v!=son[x]){
            dfs2(v,v);
        }
    }
}
int seg[4*N];
int lazy[4*N];
void push_up(int id){
    seg[id]=(seg[id<<1]+seg[id<<1|1])%p;
}
void push_down(int id,int l,int r){
    int mid=(l+r)>>1;
    seg[id<<1]=(seg[id<<1]+(mid-l+1)*lazy[id])%p;
    seg[id<<1|1]=(seg[id<<1|1]+(r-mid)*lazy[id])%p;
    lazy[id<<1]=(lazy[id<<1]+lazy[id])%p;
    lazy[id<<1|1]=(lazy[id<<1|1]+lazy[id])%p;
    lazy[id]=0;
}
void build(int id,int l,int r){
    if(l==r){
        seg[id]=ai[rk[l]];
        return ;
    }
    int mid=(l+r)>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    push_up(id);
}
void qu_add(int li,int ri,int id,int l,int r,int v){
    if(li<=l&&r<=ri){
        seg[id]=(seg[id]+(r-l+1)*v)%p;
        lazy[id]=(lazy[id]+v)%p;
        return ;
    }
    push_down(id,l,r);
    int mid=(l+r)>>1;
    if(mid>=li){ qu_add(li,ri,id<<1,l,mid,v); }
    if(mid<ri){ qu_add(li,ri,id<<1|1,mid+1,r,v); }
    push_up(id);
}
int query(int li,int ri,int id,int l,int r){
    if(li<=l&&r<=ri){
        return seg[id];
    }
    push_down(id,l,r);
    int ans=0;
    int mid=(l+r)>>1;
    if(mid>=li){ ans=(ans+query(li,ri,id<<1,l,mid))%p; }
    if(mid<ri){ ans=(ans+query(li,ri,id<<1|1,mid+1,r))%p; }
    return ans;
}
void ask1(int x,int y,int v){
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        qu_add(id[top[x]],id[x],1,1,n,v);
        x=fa[top[x]];
    }
    if(id[x]>id[y]) swap(x,y);
    qu_add(id[x],id[y],1,1,n,v);
}
int ask2(int x,int y){
    int sum=0;
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        sum=(sum+query(id[top[x]],id[x],1,1,n))%p;
        x=fa[top[x]];
    }
    if(id[x]>id[y]) swap(x,y);
    sum=(sum+query(id[x],id[y],1,1,n))%p;
    return sum;
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&r,&p);
    rep(i,1,n) scanf("%d",&ai[i]);
    rep(i,1,n-1){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v); add(v,u);
    }
    dfs1(r); dfs2(r,r);
    build(1,1,n);
    rep(i,1,m){
        int k,x,y,v;
        scanf("%d",&k);
        if(k==1){
            scanf("%d%d%d",&x,&y,&v);
            ask1(x,y,v);
        }
        if(k==2){
            scanf("%d%d",&x,&y);
            printf("%d\n",ask2(x,y));
        }
        if(k==3){
            scanf("%d%d",&x,&v);
            qu_add(id[x],id[x]+size[x]-1,1,1,n,v);
        }
        if(k==4){
            scanf("%d",&x);
            printf("%d\n",query(id[x],id[x]+size[x]-1,1,1,n));
        }
    }
    return 0;
}