NOIP快来了，复习一下。

题目描述

如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：
操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z
操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和
操作3： 格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z
操作4： 格式： 4 x 表示求以x为根节点的子树内所有节点值之和

输入输出格式

输入格式：

第一行包含4个正整数N、M、R、P，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。

接下来一行包含N个非负整数，分别依次表示各个节点上初始的数值。

接下来N-1行每行包含两个整数x、y，表示点x和点y之间连有一条边（保证无环且连通）

接下来M行每行包含若干个正整数，每行表示一个操作，格式如下：

操作1： 1 x y z

操作2： 2 x y

操作3： 3 x z

操作4： 4 x

输出格式：

输出包含若干行，分别依次表示每个操作2或操作4所得的结果（对P取模）

输入输出样例

输入样例#1：

5 5 2 24
7 3 7 8 0 
1 2
1 5
3 1
4 1
3 4 2
3 2 2
4 5
1 5 1 3
2 1 3

输出样例#1：

2
21

说明

时空限制：1s，128M

数据规模：

对于30%的数据： $N \leq 10, M \leq 10$

对于70%的数据： $ N \leq {10}^3, M \leq {10}^3$

对于100%的数据： $ N \leq {10}^5, M \leq {10}^5 $

PS

都说了是模板，当然是裸的树剖了.

坑点

先开始取模次数太少，炸了20%，不想说$~(X_X)~$.

Code:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define fill(a,b) fill(a,a+sizeof(a),b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int maxn=2e5+10;
struct edge
{
	int to,next;
	edge(){}
	edge(int to,int next):to(to),next(next){}
}e[maxn<<1];
int pre[maxn],tot=0,son[maxn]={0},top[maxn]={0},le[maxn]={0},
	dep[maxn]={0},pos[maxn]={0},sz[maxn]={0},fa[maxn]={0},
	sum[maxn<<2]={0},add[maxn<<2]={0},a[maxn],
	n,m,r,p,cnt=0,c=0;
void addedge(int,int);
void dfs(int);
void dfs(int,int);
void update(int,int,int,int,int,int);
void UP(int,int,int);
int query(int,int,int,int,int);
int getsum(int,int);
void PushUP(int);
int main()
{
//	freopen("testdata.in","r",stdin);
	fill(pre,-1);
	scanf("%d%d%d%d",&n,&m,&r,&p);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=2;i<=n;i++)
	{
		int f,t;
		scanf("%d%d",&f,&t);
		addedge(f,t),addedge(t,f);
	}
	dep[r]=1;
	dfs(r);
	dfs(r,r);
	for(int i=1;i<=n;i++)
	{
		update(pos[i],pos[i],a[i],1,n,1);
	}
	while(m--)
	{
		int op,x,y,z;
		scanf("%d",&op);
		if(op==1) scanf("%d%d%d",&x,&y,&z),UP(x,y,z);
		else if(op==2) scanf("%d%d",&x,&y),printf("%d\n",getsum(x,y)%p);
		else if(op==3) scanf("%d%d",&x,&y),update(pos[x],le[x],y,1,n,1);
		else scanf("%d",&x),printf("%d\n",query(pos[x],le[x],1,n,1)%p);
	}
	return 0;
}
void addedge(int from,int to)
{
	e[++tot]=edge(to,pre[from]);pre[from]=tot;
}
void dfs(int s)
{
	sz[s]=1,son[s]=0;
	for(int i=pre[s];~i;i=e[i].next)
	{
		int &ito=e[i].to;
		if(ito==fa[s]) continue;
		fa[ito]=s;
		dep[ito]=dep[s]+1;
		dfs(ito);
		if(sz[ito]>sz[son[s]]) son[s]=ito;
		sz[s]+=sz[ito];
	}
}
void dfs(int s,int tp)
{
	top[s]=tp;
	le[s]=pos[s]=++cnt;
	if(son[s]) dfs(son[s],tp),le[s]=max(le[s],le[son[s]]);
	for(int i=pre[s];~i;i=e[i].next)
	{
		int &ito=e[i].to;
		if(ito==fa[s]||ito==son[s]) continue;
		dfs(ito,ito),le[s]=max(le[s],le[ito]);
	}
}
void PushUP(int rt)
{
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void PushDown(int rt,int m)
{
	if(add[rt])
	{
		add[rt<<1]+=add[rt]%p;add[rt<<1]%=p;
		add[rt<<1|1]+=add[rt]%p;add[rt<<1|1]%=p;
		sum[rt<<1]+=add[rt]*(m-(m>>1))%p;sum[rt<<1]%=p;
		sum[rt<<1|1]+=add[rt]*(m>>1)%p;sum[rt<<1|1]%=p;
		add[rt]=0;
	}
}
void update(int L,int R,int val,int l,int r,int rt)
{
	if(L<=l&&r<=R)
	{
		add[rt]=(add[rt]+val%p)%p;
		sum[rt]=(sum[rt]+val*(r-l+1)%p)%p;
		return;
	}
	PushDown(rt,r-l+1);
	int m=(l+r)>>1;
	if(L<=m) update(L,R,val,lson);
	if(R>m) update(L,R,val,rson);
	PushUP(rt);
}
int query(int L,int R,int l,int r,int rt)
{
	if(L<=l&&r<=R) return sum[rt]%=p;
	PushDown(rt,r-l+1);
	int m=(l+r)>>1,ret=0;
	if(L<=m) ret=(ret+query(L,R,lson)%p)%p;//L<=m NO! L<=l
	if(R>m) ret=(ret+query(L,R,rson)%p)%p;
	return ret;
}
int getsum(int x,int y)
{
	int fx=top[x],fy=top[y];
	int tmp=0;
	while(fx!=fy)
	{
		if(dep[fx]<dep[fy]) swap(fx,fy),swap(x,y);
		tmp=(tmp+query(pos[fx],pos[x],1,n,1)%p)%p;
		x=fa[fx],fx=top[x];
	}
	if(dep[x]>dep[y]) swap(x,y);
	return tmp=(tmp+query(pos[x],pos[y],1,n,1)%p)%p;
}
void UP(int x,int y,int val)
{
	int fx=top[x],fy=top[y];
	while(fx!=fy)
	{
		if(dep[fx]<dep[fy]) swap(fx,fy),swap(x,y);
		update(pos[fx],pos[x],val,1,n,1);
		x=fa[fx],fx=top[x];
	}
	if(dep[x]>dep[y]) swap(x,y);
	update(pos[x],pos[y],val,1,n,1);
}