如题，已知一棵包含N个结点的树(连通且无环),每个节点上包含一 个数值, 需要支持以下操作 :
操作1 :格式: 1 x y z表示将树从x到y结点最短路径上所有节点的值都加上z
操作2 :格式: 2 x y表示求树从x到y结点最短路径上所有节点的值之和
操作3:格式: 3 x z表示将以为根节点的子树内所有节点值都加上z
操作4:格式: 4 x表示求以x为根节点的子树内所有节点值之和做国家集训队的题的时候发现打炸了
感觉自己树剖有点问题
所以又跑过去刷刷树剖
这么简单的东西就不写多了
代码：
#include<bits/stdc++.h>
#define N 200005
#define ll long long
#define mid ((l+r)>>1)
#define len (r-l+1)
using namespace std;
int n,m,root,mod,u,v,w,opt,x,y,z;
int a[N];
struct Edge
{
int next,to;
}edge[N<<1];
int cnt=0,head[N];
inline void add_edge(int from,int to)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
head[from]=cnt;
}
template<class T>inline void read(T &res)
{
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
/*树链剖分的两个dfs*/
int dep[N],fa[N],size[N],son[N];
void dfs1(int u,int f)
{
fa[u]=f;
size[u]=1;
dep[u]=dep[f]+1;
for(register int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==f) continue;
dfs1(v,u);
size[u]+=size[v];
if(size[son[u]]<size[v]) son[u]=v;
}
}
int seg[N],rev[N],top[N];
void dfs2(int u)
{
int v=son[u];
if(v)
{
seg[v]=++seg[0];//每个点新的编号
rev[seg[0]]=v;
top[v]=top[u];//这个点所在链的顶端
dfs2(v);
}
for(register int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(!top[v])
{
seg[v]=++seg[0];
rev[seg[0]]=v;
top[v]=v;
dfs2(v);
}
}
}
/*线段树部分*/
int sum[N<<2],add[N<<2];
void pushup(int rt) {sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%mod;}//向上更新线段树
void add_add(int rt,int l,int r,int v)//加法标记更新
{
add[rt]=(add[rt]+v)%mod;
sum[rt]=(sum[rt]+v*len)%mod;
}
void pushdown(int rt,int l,int r)//标记下放
{
if(!add[rt]) return;
add_add(rt<<1,l,mid,add[rt]);
add_add(rt<<1|1,mid+1,r,add[rt]);
add[rt]=0;//记得清零
}
void modify(int rt,int l,int r,int x,int y,int v)//调整
{
if(l>y||r<x) return;
if(x<=l&&y>=r)
{
add_add(rt,l,r,v);
return;
}
pushdown(rt,l,r);
modify(rt<<1,l,mid,x,y,v);
modify(rt<<1|1,mid+1,r,x,y,v);
pushup(rt);
}
int query(int rt,int l,int r,int x,int y)//求和
{
if(l>y||r<x) return 0;
if(x<=l&&y>=r) return sum[rt]%mod;
pushdown(rt,l,r);
return ( query(rt<<1,l,mid,x,y) + query(rt<<1|1,mid+1,r,x,y) )%mod;
}
void build(int rt,int l,int r)//建树
{
if(l==r)
{
sum[rt]=a[rev[l]];
return;
}
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
pushup(rt);
}
/*主体部分*/
void modify_edge(int x,int y,int v)//链修改
{
int fx=top[x];
int fy=top[y];
while(fx!=fy)
{
if(dep[fx]<dep[fy])
{
swap(fx,fy);
swap(x,y);
}
modify(1,1,seg[0],seg[fx],seg[x],v);
x=fa[fx];
fx=top[x];
}
if(dep[x]>dep[y]) swap(x,y);
modify(1,1,seg[0],seg[x],seg[y],v);
}
int ask_edge(int x,int y)//链查询
{
int fx=top[x];
int fy=top[y];
int res=0;
while(fx!=fy)
{
if(dep[fx]<dep[fy])
{
swap(fx,fy);
swap(x,y);
}
res=(res+query(1,1,seg[0],seg[fx],seg[x]))%mod;
x=fa[fx];
fx=top[x];
}
if(dep[x]>dep[y]) swap(x,y);
res=(res+query(1,1,seg[0],seg[x],seg[y]))%mod;
return res;
}
void modify_tree(int rt,int v)//树修改
{
modify(1,1,seg[0],seg[rt],seg[rt]+size[rt]-1,v%mod);
}
int ask_tree(int rt)//树查询
{
return query(1,1,seg[0],seg[rt],seg[rt]+size[rt]-1)%mod;
}
void init()
{
seg[0]=seg[root]=1;
top[root]=root;
rev[1]=root;
dfs1(root,0);
dfs2(root);
build(1,1,seg[0]);
}
int main()
{
read(n);read(m);read(root);read(mod);
for(register int i=1;i<=n;++i) read(a[i]),a[i]%=mod;
for(register int i=1;i<=n-1;++i)
{
read(u);read(v);
add_edge(u,v);
add_edge(v,u);
}
init();
for(register int i=1;i<=m;++i)
{
read(opt);
if(opt==1)//链增加
{
read(x);read(y);read(z);
modify_edge(x,y,z);
}
else if(opt==2)//链查询最小值
{
read(x);read(y);
printf("%d\n",ask_edge(x,y));
}
else if(opt==3)//树增加
{
read(x);read(z);
modify_tree(x,z);
}
else if(opt==4)//树求和
{
read(x);
printf("%d\n",ask_tree(x));
}
}
return 0;
}
/*
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
*/