一.写在文前
前置芝士：线段树，另外可能学了LCA会更好理解一点
树链剖分的板子就是基于线段树哒！不会的读者先去学习它再来看下面的部分叭！qwq
先阅读下板子题叭！
二.一些有用的变量
可能看起来有点怪怪的，但下面都会讲到各自的用途的，先大概了解下变量叭
id[N]表示树上某个点的时间戳（即第几个被访问）
fa[N]表示此点的父亲节点
sz[N]表示以某个节点为根的子树的大小，即其中共有几个点
son[N]表示其重儿子，即其子节点中sz最大的儿子的标号，若有两个儿子的sz相同，随便取其中的一个即可，这个无所谓
dep[N]表示节点的深度
top[N]表示一条重链的开端，其中重链为从一个轻节点开始不断向下面的重儿子拓展得到的一串链，所以其开端也就是一个轻节点
wa[N]表示一个时间戳所对应的值
三.dfs1
void dfs1(int x,int f,int d)
{
fa[x]=f;
dep[x]=d;
sz[x]=1;
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(y==f)
continue;
dfs1(y,x,d+1);
sz[x]+=sz[y];
if(sz[y]>sz[son[x]])
son[x]=y;
}
}
先初始化一些变量，再dfs下去，由此回溯后求出sz，再找到x的重儿子，如此可以保证重儿子与其父节点的时间戳为连续的（访问顺序就是这样的哇），为以后线段树的维护作铺垫，应该蛮好理解的，就不做过多赘述了
四.dfs2
void dfs2(int x,int topf)
{
id[x]=++cnt;
wa[cnt]=a[x];
top[x]=topf;
if(!son[x])
return ;
dfs2(son[x],topf);
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(y==fa[x]||y==son[x])
continue;
dfs2(y,y);
}
}
cnt用来标记每个节点的时间戳,给wa[cnt]传入所输入的初始值，一直向着重儿子方向走，更新每个重儿子的top,再向其他轻儿子走去，因为是轻儿子，所以它所在的重链肯定与其父亲不在一条上，所以自然是它自己作为重链的开端，向下拓展其重链
五.queryRange
int queryRange(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
int res=query(1,id[top[x]],id[x]);
ans+=res;
ans%=p;
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
int res=query(1,id[x],id[y]);
ans+=res;
return ans%p;
}
好的，我们终于来到了树链剖分最重要的部分了！前面的两次dfs都是为了这一步的操作！
对于while，其实就是深度大的那个点向上爬树（2333有点形象吧），重链就是一条条绳子,一路上加上路上的值，然后最后让x，y变成同一条重链上的点，我们知道重链上的点的时间戳肯定是连续的（没懂的再回上面看看吧！），所以这一段区间的值可用线段树维护，同理，在x每次攀爬到其所在重链的顶端之上时，这一段区间也是可以用线段树维护的！而此时x也脱离了它原本的重链，成为了上面的重链的末尾，慢慢的x，y就变成一条链上的了。
注：每次更新深度深的，因为它落后了对吧！
这里挺重要的啊，读者请认真思考下啦！qwq
六.updateRange
void updateRange(int x,int y,int z)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
change(1,id[top[x]],id[x],z);
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
change(1,id[x],id[y],z);
}
一样的，就不多说啦！
七.对于一个子树的修改即查询
change(1,id[x],id[x]+sz[x]-1,y);
根据我们的dfs顺序，一个节点x的子树的时间戳肯定是连续的，那修改的区间也就好办了，就是上面写的
八.AC-CODE
终于讲的差不多了！接下来直接上代码!方便读者对于一些细节部分的理解吧！
当然也为了方便你们调代码doge
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,r,p,a[N];
int tot,head[N],ver[N*2],Next[N*2];
int cnt,id[N],fa[N],son[N],dep[N],sz[N],top[N],wa[N];
struct node{
int le,ri;
int sum1,tag;
}tree[4*N+5];
void build(int k,int l,int r){
tree[k].le=l;tree[k].ri=r;
if(l==r){
tree[k].sum1=wa[l];
return ;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
tree[k].sum1=tree[k<<1].sum1+tree[k<<1|1].sum1;
}
void lazy_tag(int k){
if(tree[k].tag!=0){
tree[k<<1].tag+=tree[k].tag;
tree[k<<1|1].tag+=tree[k].tag;
tree[k<<1].sum1+=tree[k].tag*(tree[k<<1].ri-tree[k<<1].le+1);
tree[k<<1|1].sum1+=tree[k].tag*(tree[k<<1|1].ri-tree[k<<1|1].le+1);
tree[k].tag=0;
}
}
void change(int k,int l,int r,int w){
if(l<=tree[k].le&&r>=tree[k].ri){
tree[k].tag+=w;
tree[k].sum1+=w*(tree[k].ri-tree[k].le+1);
return ;
}
lazy_tag(k);
int mid=(tree[k].le+tree[k].ri)>>1;
if(l<=mid)change(k<<1,l,r,w);
if(r>mid)change(k<<1|1,l,r,w);
tree[k].sum1=(tree[k<<1].sum1+tree[k<<1|1].sum1)%p;
}
int query(int k,int l,int r){
if(l<=tree[k].le&&r>=tree[k].ri){
return tree[k].sum1%p;
}
lazy_tag(k);
int mid=(tree[k].le+tree[k].ri)>>1;
int ans=0;
if(l<=mid)ans+=query(k<<1,l,r);
if(r>mid)ans+=query(k<<1|1,l,r);
ans=ans%p;
return ans;
}
void add(int x,int y)
{
ver[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
}
void dfs1(int x,int f,int d)
{
fa[x]=f;
dep[x]=d;
sz[x]=1;
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(y==f)
continue;
dfs1(y,x,d+1);
sz[x]+=sz[y];
if(sz[y]>sz[son[x]])
son[x]=y;
}
}
void dfs2(int x,int topf)
{
id[x]=++cnt;
wa[cnt]=a[x];
top[x]=topf;
if(!son[x])
return ;
dfs2(son[x],topf);
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(y==fa[x]||y==son[x])
continue;
dfs2(y,y);
}
}
int queryRange(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
int res=query(1,id[top[x]],id[x]);
ans+=res;
ans%=p;
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
int res=query(1,id[x],id[y]);
ans+=res;
return ans%p;
}
void updateRange(int x,int y,int z)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
change(1,id[top[x]],id[x],z);
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
change(1,id[x],id[y],z);
}
int main()
{
scanf("%d%d%d%d",&n,&m,&r,&p);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs1(r,0,1);
dfs2(r,r);
build(1,1,cnt);
for(int i=1;i<=m;i++)
{
int opt;
scanf("%d",&opt);
if(opt==1)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
updateRange(x,y,z);
}
if(opt==2)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",queryRange(x,y)%p);
}
if(opt==3)
{
int x,y;
scanf("%d%d",&x,&y);
change(1,id[x],id[x]+sz[x]-1,y);
}
if(opt==4)
{
int x;
scanf("%d",&x);
printf("%d\n",query(1,id[x],id[x]+sz[x]-1)%p);
}
}
return 0;
}