P3384

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int Maxn = 2e5+10;
int n,m,r,Mod,res;
int e,head[Maxn],net[Maxn],to[Maxn],w[Maxn],wt[Maxn];
int son[Maxn],id[Maxn],fa[Maxn],cnt,dep[Maxn],siz[Maxn],top[Maxn];
struct node{
	int l,r;
	long long w,lazy;
}tree[Maxn<<2];
inline void add(int x,int y)
{
	to[++e]=y;
	net[e]=head[x];
	head[x]=e;
}
inline void push_down(int k)
{
	if(tree[k].l==tree[k].r)
	{
		tree[k].lazy=0;
		return;
	}
	tree[k*2].w+=(tree[k*2].r-tree[k*2].l+1)*tree[k].lazy;
	tree[k*2+1].w+=(tree[k*2+1].r-tree[k*2+1].l+1)*tree[k].lazy;
	tree[k*2].lazy+=tree[k].lazy;
	tree[k*2+1].lazy+=tree[k].lazy;
	tree[k*2].w%=Mod;
	tree[k*2+1].w%=Mod;
	tree[k].lazy=0;
}
inline void update(int k)
{
	tree[k].w=(tree[k*2].w+tree[k*2+1].w)%Mod;
}
inline void build(int k,int l,int r)
{
	tree[k].l=l;
	tree[k].r=r;
	if(l==r)
	{
		tree[k].w=wt[l];
		tree[k].w%=Mod;
		return;
	}
	int mid=(l+r)>>1;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
	update(k);
}
inline ll query_qujian(int k,int l,int r)
{
	if(tree[k].l==l&&tree[k].r==r)
		return tree[k].w;
	push_down(k);
	int mid=(tree[k].l+tree[k].r)>>1;
	if(r<=mid)
		return query_qujian(k*2,l,r);
	else if(l>mid)
		return query_qujian(k*2+1,l,r);
	else
		return query_qujian(k*2,l,mid)+query_qujian(k*2+1,mid+1,r); 
}
inline void change_qujian(int k,int l,int r,int x)
{
	if(tree[k].l==l&&tree[k].r==r)
	{
		tree[k].w+=(r-l+1)*x;
		tree[k].lazy+=x;
		return;
	}
	push_down(k);
	int mid=(tree[k].l+tree[k].r)>>1;
	if(r<=mid)
		change_qujian(k*2,l,r,x);
	else if(l>mid)
		change_qujian(k*2+1,l,r,x);
	else
	{
		change_qujian(k*2,l,mid,x);
		change_qujian(k*2+1,mid+1,r,x); 
	}
	update(k);
}
//以上线段树 
inline ll lu_jing_query(int x,int y)
{
	int ans=0;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		ans+=query_qujian(1,id[top[x]],id[x]);
		ans%=Mod;
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])
		swap(x,y);
	ans+=query_qujian(1,id[x],id[y]);
	ans%=Mod;
	return ans;
}
inline void lu_jing_add(int x,int y,int k)
{
	k%=Mod;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		change_qujian(1,id[top[x]],id[x],k);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])
		swap(x,y);
	change_qujian(1,id[x],id[y],k);
}
inline ll query_son_tree(int x)
{
	return query_qujian(1,id[x],id[x]+siz[x]-1)%Mod;
}
inline void change_son_tree(int x,int k)
{
	change_qujian(1,id[x],id[x]+siz[x]-1,k);
}
inline void dfs1(int x,int f,int deep)
{
	dep[x]=deep;
	fa[x]=f;
	siz[x]=1;
	int maxson=-1;
	for(int i=head[x];i;i=net[i])
	{
		int y=to[i];
		if(y==f)
			continue;
		dfs1(y,x,deep+1);
		siz[x]+=siz[y];
		if(siz[y]>maxson)
			son[x]=y,maxson=siz[y];
	}
}
inline void dfs2(int x,int topf)
{
	id[x]=++cnt;
	wt[cnt]=w[x];
	top[x]=topf;
	if(!son[x])
		return;
	dfs2(son[x],topf);
	for(int i=head[x];i;i=net[i])
	{
		int y=to[i];
		if(y==fa[x]||y==son[x])
			continue;
		dfs2(y,y);
	}
}
int main()
{
	cin>>n>>m>>Mod;
	for(int i=1;i<=n;i++)
		cin>>w[i];
	for(int i=1;i<=n;i++)
	{
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	dfs1(r,0,1);
	dfs2(r,r);
	build(1,1,n);
	while(m--)
	{
		int op,x,y,z;
		cin>>op;
		if(op==1)//路径加 
		{
			cin>>x>>y>>z;
			lu_jing_add(x,y,z);
		}
		else if(op==2)
		{
			cin>>x>>y;
			cout<<lu_jing_query(x,y);
		}
		else if(op==3)
		{
			cin>>x>>y;
			change_son_tree(x,y);
		}
		else
		{
			cin>>x;
			cout<<query_son_tree(x);
		}
	}
	return 0;
}

Code

钱去找 @cccyyyxxx