【模板】轻重链剖分/树链剖分

题目大意

已知一棵包含 $N$ 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：

1 x y z，表示将树从 $x$ 到 $y$ 结点最短路径上所有节点的值都加上 $z$。

2 x y，表示求树从 $x$ 到 $y$ 结点最短路径上所有节点的值之和。

3 x z，表示将以 $x$ 为根节点的子树内所有节点值都加上 $z$。

4 x 表示求以 $x$ 为根节点的子树内所有节点值之和

思路

使用树剖，将一棵树变成一条条互不相交的链进行维护

每条链上的下标连续，每棵子树的所有节点的下标连续，之后就可以使用线段树或者树状数组进行维护。

代码

#include<bits/stdc++.h>
#define Inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int MAXX=100005;

int m,R;

//树状数组+树剖
int n;
LL mod,a[MAXX];
vector<int> to[MAXX];
//树状数组
LL c1[MAXX],c2[MAXX];
inline int lowbit(int x){
    return x&(-x);
}
inline void add(int l,int r,int x){
    x %= mod;
    int ad1 = (LL)(l-1)*x%mod;
    int ad2 = (LL)r*x%mod;
    for(int t=l;t<=n;t+=lowbit(t)){
        c1[t] = (c1[t]+x)%mod;
        c2[t] = (c2[t]+ad1)%mod;
    }
    for(int t=r+1;t<=n;t+=lowbit(t)){
        c1[t] = (c1[t]-x)%mod;
        c1[t] = (c1[t]+mod)%mod;
        c2[t] = (c2[t]-ad2)%mod;
        c2[t] = (c2[t]+mod)%mod;
    }
}
inline int qwq(int i){ //qwq
    int res = 0;
    for(int t=i;t>0;t-=lowbit(t)){
        res = (res+(LL)i*c1[t]%mod)%mod;
        res = (res-c2[t])%mod;
        res = (res+mod)%mod;
    }
    return res;
}
inline int query(int l,int r){
    int res = (qwq(r)-qwq(l-1))%mod;
    return (res+mod)%mod;
}
//树剖
int depth[MAXX],num[MAXX],son[MAXX],fa[MAXX];
int top[MAXX],id[MAXX];
void dfs1(int now,int fa){
	depth[now]=depth[::fa[now]=fa]+1;
	num[now]=1;
	int maxnum=0;
	for(int jj:to[now]){
		if(jj==fa) continue;
		dfs1(jj,now);
		num[now]+=num[jj];
		if(num[jj]>maxnum){
			son[now]=jj;
			maxnum=num[jj];
		}
	}
}
int cnt=0;
void dfs2(int now,int t){
	top[now]=t;
	id[now]=++cnt;
	if(a[now])
		add(id[now],id[now],a[now]);
	if(son[now])
		dfs2(son[now],t);
	for(int jj:to[now]){
		if(jj==son[now]||jj==fa[now]) continue;
		dfs2(jj,jj);
	}
}
inline void init(int root){//root为根节点
	dfs1(root,0);
	dfs2(root,root);
}
void addpath(int l,int r,LL jk){
	while(top[l]!=top[r]){
		if(depth[top[l]]<depth[top[r]])
			swap(l,r);
		add(id[top[l]],id[l],jk);
		l=fa[top[l]];
	}
	if(depth[l]>depth[r])
		swap(l,r);
	add(id[l],id[r],jk);
}
LL getsum(int l,int r){
	LL ret=0LL;
	while(top[l]!=top[r]){
		if(depth[top[l]]<depth[top[r]])
			swap(l,r);
		ret=(ret+query(id[top[l]],id[l]))%mod;
		l=fa[top[l]];
	}
	if(depth[l]>depth[r])
		swap(l,r);
	ret=(ret+query(id[l],id[r]))%mod;
	return ret;
}
void addtree(int x,LL jk){
	add(id[x],id[x]+num[x]-1,jk);
}
LL getsum(int x){
	return query(id[x],id[x]+num[x]-1);
}


inline void solve(){
	scanf("%d%d%d%lld",&n,&m,&R,&mod);
	for(int i=1;i<=n;++i)
		scanf("%lld",&a[i]);
	for(int i=1;i<n;++i){
		int jj,kk;scanf("%d%d",&jj,&kk);
		to[jj].emplace_back(kk);
		to[kk].emplace_back(jj);
	}

	init(R);

	while(m--){
		int ch;scanf("%d",&ch);
		if(ch==1){
			int l,r;LL jk;
			scanf("%d%d%lld",&l,&r,&jk);
			addpath(l,r,jk);
		}
		else if(ch==2){
			int l,r;scanf("%d%d",&l,&r);
			printf("%lld\n",getsum(l,r));
		}
		else if(ch==3){
			int x;LL jk;
			scanf("%d%lld",&x,&jk);
			addtree(x,jk);
		}
		else{
			int x;scanf("%d",&x);
			printf("%lld\n",getsum(x));
		}
	}
}

signed main(){
//	LL t;scanf("%lld",&t);
//	while(t--)
		solve();
	
	return 0;
}