代码

#include<bits/stdc++.h>
#define N 100005
#define int long long 
using namespace std;
//--------------------------------------初始化 
//全局变量 
	int n,m,s,mod;
	 
//树 
	vector<signed>g[N];
	signed a[N],tmp[N];

//重链剖分 
	//dfs1
	signed f[N];//父亲 
	signed size[N];//子树大小 
	signed hson[N];//重儿子 
	signed deep[N];//深度 
	//dfs2
	signed dfn[N],tot=0;//dfn序 
	signed top[N];//链顶 

//线段树 
	int tree[N<<2];
	int lazy[N<<2];

//--------------------------------------dfs
void dfs1(int u,int fa)
{
	//主线任务:找重儿子 
	f[u]=fa;
	size[u]=1;
	deep[u]=deep[fa]+1;
	for(auto v:g[u])
	{
		if(v==fa)continue;
		dfs1(v,u);
		size[u]+=size[v];
		if(size[v]>size[hson[u]])//有更好的重儿子 
			hson[u]=v;
	}
}
void dfs2(int u,int fa)
{
	//主线任务:找重链 
	dfn[u]=++tot;
	a[tot]=tmp[u];
	top[u]=fa;
	if(!hson[u])return;//叶结点不必遍历
	dfs2(hson[u],fa);//重儿子继承"家产"
	for(auto v:g[u])
	{
		if(v==f[u] || v==hson[u])continue;
		dfs2(v,v);//非重儿子自己开一个新的"家业"
	}
}

//--------------------------------------线段树 
void push_up(int x)
{
	tree[x]=tree[x<<1]+tree[x<<1|1];
}
int push_down(int s,int t,int x)
{
	int m=(s+t)>>1;
	if(lazy[x])
	{
		tree[x<<1]+=lazy[x]*(m-s+1);
		tree[x<<1|1]+=lazy[x]*(t-m);
		lazy[x<<1]+=lazy[x];
		lazy[x<<1|1]+=lazy[x];
		lazy[x]=0;
	}
	return m;
}
void btree(int l,int r,int x)
{
	if(l==r)
	{
		tree[x]=a[l];//这里不是a[dfn[l]] 
		return;
	}
	int m=(l+r)>>1;
	btree(l,m,x<<1);
	btree(m+1,r,x<<1|1);
	push_up(x);
}
int gtree(int l,int r,int s,int t,int x)
{
	if(l<=s && t<=r)
		return tree[x];
	int m=push_down(s,t,x),sum=0;
	if(l<=m)sum+=gtree(l,r,s,m,x<<1);
	if(r>m)sum+=gtree(l,r,m+1,t,x<<1|1);
	return sum;
}
void utree(int l,int r,int s,int t,int c,int x)
{
	if(l<=s && t<=r)
	{
		tree[x]+=c*(t-s+1);
		lazy[x]+=c;
		return;
	}
	int m=push_down(s,t,x);
	if(l<=m)utree(l,r,s,m,c,x<<1);
	if(r>m)utree(l,r,m+1,t,c,x<<1|1);
	push_up(x);
}
void btree()
{
	btree(1,n,1);
}
int gtree(int l,int r)
{
	return gtree(l,r,1,n,1);
}
void utree(int l,int r,int c)
{
	utree(l,r,1,n,c,1);
}

//--------------------------------------4种操作 
void uzlpf(int u,int v,int c)//第1种操作 
{
	while(top[u]!=top[v])
	{
		if(deep[top[u]]<deep[top[v]])
			swap(u,v);
		utree(dfn[top[u]],dfn[u],c);//top[u]放前面,不然有问题
		u=f[top[u]];
	}
	if(deep[u]<deep[v])
		swap(u,v);
	utree(dfn[v],dfn[u],c);//v放前面,不然有问题
}
int gzlpf(int u,int v)//第2种操作 
{
	int sum=0;
	while(top[u]!=top[v])
	{
		if(deep[top[u]]<deep[top[v]])
			swap(u,v);
		sum+=gtree(dfn[top[u]],dfn[u]);
		u=f[top[u]];
	}
	if(deep[u]<deep[v])
		swap(u,v);
	sum+=gtree(dfn[v],dfn[u]);
	return sum;
}
void uzs(int u,int c)//第3种操作 
{
	utree(dfn[u],dfn[u]+size[u]-1,c);//dfn+size-1就是子树大小
}
int gzs(int u)//第4种操作 
{
	return gtree(dfn[u],dfn[u]+size[u]-1);
}

//--------------------------------------主函数 
signed main()
{
	cin>>n>>m>>s>>mod;
	for(int i=1;i<=n;i++)
		cin>>tmp[i];
	for(int i=1;i<n;i++)
	{
		int u,v;cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs1(s,0);//别忘写了
	dfs2(s,0);
	btree();
	while(m--)
	{
		int o,x,y,z;
		cin>>o;
		if(o==1)
		{
			cin>>x>>y>>z;
			uzlpf(x,y,z);
		}
		else if(o==2)
		{
			cin>>x>>y;
			cout<<gzlpf(x,y)%mod<<"\n";
		}
		else if(o==3)
		{
			cin>>x>>z;
			uzs(x,z);
		}
		else
		{
			cin>>x;
			cout<<gzs(x)%mod<<"\n";
		}
	}
	return 0;
}

司陆

在给树做子树加减的时候，可以使用重(zhong)链剖分，让一段区域的DFS序是连续的。
接着，直接衔接==线段~树~~~==区间修改、求和。

呆码

#include<bits/stdc++.h>
#define N 200005
#define int long long 
using namespace std;
int top[N];
int dfs[N];
int fat[N];
int siz[N];
int dep[N];
int hsn[N];
int out[N];
int n,m,r,p;
namespace xds{
	struct node{
		int l,r;
		int num;
	}tree[N*4];
	int a[N]={},n,tag[N];
	void ctf(int c){
		tree[c].num=tree[c<<1].num+tree[(c<<1)+1].num;
	}
	void createTree(int sp,int l,int r){
		tree[sp].l=l;
		tree[sp].r=r;
		if(l==r){
			tree[sp].num=a[l];
			return;
		}
		int mid=(l+r)>>1;
		createTree(sp<<1,l,mid);
		createTree((sp<<1)+1,mid+1,r);
		ctf(sp);
	}
	void cltag(int sp){
		int mid=(tree[sp].l+tree[sp].r)>>1;
		if(tag[sp]){
			tree[sp<<1].num+=tag[sp]*(mid-tree[sp].l+1);
			tree[(sp<<1)+1].num+=tag[sp]*(tree[sp].r-mid);
			tag[sp<<1]+=tag[sp];
			tag[(sp<<1)+1]+=tag[sp];
			tag[sp]=0;
		}
	}
	void pointChange(int sp,int pt,int nn){
		if(tree[sp].l==tree[sp].r){
			tree[sp].num+=nn;
			return;
		}
		int mid=(tree[sp].l+tree[sp].r)>>1;
		if(pt<=mid)pointChange(sp<<1,pt,nn);
		else pointChange((sp<<1)+1,pt,nn);
		ctf(sp);
	}
	void areaChange(int sp,int l,int r,int c){
		if(tree[sp].l>=l&&tree[sp].r<=r){
			tree[sp].num+=(tree[sp].r-tree[sp].l+1)*c;
			tag[sp]+=c;
			return;
		}
		cltag(sp);
		int mid=(tree[sp].l+tree[sp].r)>>1;
		if(l<=mid){
			areaChange(sp<<1,l,r,c);
		}
		if(mid<r){
			areaChange((sp<<1)+1,l,r,c);
		}
		ctf(sp);
	}
	int areaAsk(int sp,int l,int r){
		if(tree[sp].l>=l&&tree[sp].r<=r)return tree[sp].num;
		cltag(sp);
		int mid=(tree[sp].l+tree[sp].r)>>1,maxn=0;
		if(l<=mid){
			maxn=maxn+areaAsk(sp<<1,l,r);
		}
		if(mid<r){
			maxn=maxn+areaAsk((sp<<1)+1,l,r);
		}
		return maxn;
	}
}
vector<int>edge[N];
int tmp[N];
void dfs1(int num,int f);
void dfs2(int num,int f);
void init(){
	cin>>n>>m>>r>>p;
	for(int i=1;i<=n;i++)
		cin>>tmp[i];
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		edge[u].emplace_back(v);
		edge[v].emplace_back(u);
	}
	dfs1(r,0);
	dfs2(r,0);
	xds::createTree(1,1,n);
}
void dfs1(int num,int f){
	fat[num]=f;
	siz[num]=1;
	dep[num]=dep[f]+1;
	int hs=-1;
	for(auto i:edge[num]){
		if(i==f)continue;
		dfs1(i,num);
		siz[num]+=siz[i];
		if(siz[i]>hs){
			hsn[num]=i,hs=siz[i];
		}
	}
}
void dfs2(int num,int f){
	dfs[num]=++dfs[0];
	xds::a[dfs[num]]=tmp[num];
	top[num]=f;
	out[num]=dfs[0];
	if(!hsn[num])return;
	dfs2(hsn[num],f);
	for(auto i:edge[num]){
		if(i==fat[num]||i==hsn[num])continue;
		dfs2(i,i);
	}
	out[num]=dfs[0];
}
void treeAdd(int u,int v,int adn){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		xds::areaChange(1,dfs[top[u]],dfs[u],adn);
		u=fat[top[u]];
	}
	if(dep[u]<dep[v])swap(u,v);
	xds::areaChange(1,dfs[v],dfs[u],adn);
}
void subtreeAdd(int u,int adn){
	xds::areaChange(1,dfs[u],out[u],adn);
}
int treeAsk(int u,int v){
	int sum=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		sum+=xds::areaAsk(1,dfs[top[u]],dfs[u]);
		u=fat[top[u]];
	}
	if(dep[u]<dep[v])swap(u,v);
	sum+=xds::areaAsk(1,dfs[v],dfs[u]);
	return sum;
}
int subtreeAsk(int u){
	return xds::areaAsk(1,dfs[u],out[u]);
}




signed main(){
//	cin.tie(0);cout.tie(0);
//	ios::sync_with_stdio(false);
	init();
	
	//debug
	// cout<<"Pt :";
	// for(int i=1;i<=n;i++)cout<<tmp[i]<<" ";
	// cout<<"\nST :";
	// for(int i=1;i<=n;i++)cout<<xds::areaAsk(1,i,i)<<" ";
	// cout<<"\nDFS:";
	// for(int i=1;i<=n;i++)cout<<dfs[i]<<" ";
	//debug
	
	while(m--){
		int x,y,z;
		int mode;
		cin>>mode;
		switch(mode){
		case 1:
			cin>>x>>y>>z;
			treeAdd(x,y,z);
			break;
		case 2:
			cin>>x>>y;
			cout<<treeAsk(x,y)%p<<endl;
			break;
		case 3:
			cin>>x>>y;
			subtreeAdd(x,y);
			break;
		case 4:
			cin>>x;
			cout<<subtreeAsk(x)%p<<endl;
			break;
		}
	}
}

注意事项

1.不开long long见祖宗 ———————PWM
2.输出要模！
3.小心忘判断两数相反的情况