这么长一个树剖死循环了，呜呜呜！
https://www.luogu.com.cn/problem/P3384
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,R,P,id[N],cnt,fa[N],top[N],a[N],a_new[N],siz[N],son[N],dep[N];
int tree[4*N],tag[4*N];
vector<int>v[N];
//下面是线段树
void lazy(int l,int r,int now,int k)//更新
{
tree[now]+=k*(r-l+1);
tree[now]%=P;
tag[now]+=k;
tag[now]%=P;
}
void push_down(int l,int r,int now)//更新后代，下传懒标记
{
int mid=(l+r)/2;
lazy(l,mid,now*2,tag[now]);
lazy(mid+1,r,now*2+1,tag[now]);
//左右儿子分别更新
tag[now]=0;//懒标记清零
}
void push_up(int now)//更新祖先
{
tree[now]=tree[now*2]+tree[now*2+1];
tree[now]%=P;
}
void build(int l,int r,int now)//线段树建树
{
if(l==r)
{
tree[now]=a_new[l]%P;
return;
}
int mid=(l+r)/2;
build(l,mid,now*2);
build(mid+1,r,now*2+1);
push_up(now);
}
void update(int l,int r,int nl,int nr,int now,int k)//区间加
{
if(nl<=l&&r<=nr)//当前区间被修改区间包含
{
lazy(l,r,now,k);//修改当前区间
return;
}
push_down(l,r,now);//更新后代，懒标记下传
int mid=(l+r)/2;
if(mid>=l) update(l,mid,nl,nr,now*2,k);//左边有要修改的区间
if(mid<r) update(mid+1,r,nl,nr,now*2+1,k);//右边有要修改的区间
push_up(now);//更新祖先，答案上传
}
int query(int l,int r,int nl,int nr,int now)//区求和
{
int ans=0;
if(nl<=l&&r<=nr) return tree[now];//包含，直接返回
push_down(l,r,now);//更新后代，懒标记下传
int mid=(l+r)/2;
if(mid>=l) ans+=query(l,mid,nl,nr,now*2);//左边有答案
if(mid<r) ans+=query(mid+1,r,nl,nr,now*2+1);//右边有答案
return ans;//返回答案
}
//下面是树链剖分
void dfs1(int x,int father)
{
dep[x]=dep[father]+1;//预处理深度
fa[x]=father;//预处理父亲
siz[x]=1;//计算子树大小
for(auto i:v[x])
{
if(i==father) continue;
dfs1(i,x);
siz[x]+=siz[i];
if(siz[son[x]]<siz[i]) son[x]=i;//找重儿子，并记录它的编号
}
}
void dfs2(int x,int topx)
{
id[x]=++cnt;//时间戳(dfs序)
a_new[cnt]=a[x];//新的a的值
top[x]=topx;//链头
if(!son[x]) return;//叶子节点，不用继续
dfs2(son[x],topx);//先遍历重儿子
for(auto i:v[x])
{
if(i==fa[x]) continue;
if(i==son[x]) continue;
dfs2(i,i);//没个轻儿子就是链头
}
}
//下面是操作
void update_chain(int x,int y,int k)//修改链
{
while(top[x]!=top[y])//如果两点所在的重链的不一样，也就是链头不一样
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);//强制x所在链的链头深度更大
update(1,n,id[top[x]],id[x],1,k);
//因为先遍历重儿子，所以重链dfs序也是连续的，跳到链头就将这个区间加k
x=fa[top[x]];//跳到链头再跳到他的父亲，现在就在另一条重链上
}
if(dep[top[x]]<dep[top[y]]) swap(x,y);
update(1,n,id[x],id[y],1,k);//最后将x到y的区间加k
}
int query_chain(int x,int y)//链求和
{
int ans=0;
while(top[x]!=top[y])//如果两点所在的重链的不一样，也就是链头不一样
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);//强制x所在链的链头深度更大
ans+=query(1,n,id[top[x]],id[x],1);
//因为先遍历重儿子，所以重链dfs序也是连续的，跳到链头就将这个区间统计到和里
x=fa[top[x]];//跳到链头再跳到他的父亲，现在就在另一条重链上
}
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans+=query(1,n,id[x],id[y],1);//最后将x到y区间记录到答案中
return ans;//返回答案
}
void update_tree(int x,int k)//修改子树
{
update(1,n,id[x],id[x]+siz[x]-1,1,k);//子树的dfs序是连续的
}
int query_tree(int x)//子树求和
{
return query(1,n,id[x],id[x]+siz[x]-1,1);//返回子树和，子树的dfs序是连续的
}
signed main()
{
cin>>n>>m>>R>>P;
for(int i=1;i<=n;++i) cin>>a[i];
for(int i=1;i<n;++i)
{
int x,y;
cin>>x>>y;
v[x].push_back(y);
}
dfs1(R,0);
dfs2(R,R);
build(1,n,1);
while(m--)
{
int op,x,y,z;
cin>>op;
if(op==1)
{
cin>>x>>y>>z;
update_chain(x,y,z);
}
if(op==2)
{
cin>>x>>y;
cout<<query_chain(x,y)<<"\n";
}
if(op==3)
{
cin>>x>>z;
update_tree(x,z);
}
if(op==4)
{
cin>>x;
cout<<query_tree(x)<<"\n";
}
}
return 0;
}