傳送門
樹鍊剖分
樹鍊剖分就是把一顆樹分成很多條鍊，然後把鍊上的資料進行瞎搞操作（本題是用線段樹區間修改）
一步一步慢慢講：
1. 從根節點開始對整顆樹進行一次周遊
求出每個節點子樹的大小，父節點，深度和重兒子
重兒子指 兒子子樹大小最大 的兒子節點
（做這些都是為了後面瞎搞）
2. 再來一次周遊..
這次求出每個節點 所在重鍊的頂端，在dfs序中的編号（要讓重鍊的節點編号連續）以及這個編号的節點的值（節點是原樹的節點）
重鍊是指一段連續的重兒子連在一起形成的鍊,還要注意對于非重兒子節點，它本身是重鍊的起點
（做這些還是為了後面瞎搞）
3.瞎搞
本題用是線段樹搞..
那就建立線段樹
把節點在dfs序中的編号從 1 ~ n 建立線段樹
注意了，第2次周遊時重鍊的編号是連續的，是以可以用線段樹直接存重鍊的資訊
題目要區間加，區間求和，子樹加，子樹求和
區間操作就用線段樹對重鍊慢慢搞就好了
重要的是對子樹操作
還是注意第2次周遊時是深度優先周遊
是以可以發現，
對于一顆子樹，整顆子樹的編号剛好是從根節點的編号 ~ 根節點編号+子樹的大小-1（子樹的大小還包括本身）
是以根本不用管每個節點具體的編号，直接用線段樹瞎搞就OK了
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;
int n,m,roo,mo;//n為節點數，m為操作數，roo為根節點，mo為取模數
int va[100005];//節點的值
vector <int> v[100005];//v[x][i]的值表示點x到點v[x][i]有一條邊
int siz[100005],fa[100005],dep[100005],son[100005];
//siz[x]表示以x為根節點（包括本身）的子樹的節點數
//fa[x]表示點x的父節點
//dep[x]表示x的深度（根節點深度為1）
//son[x]表示點x的重兒子的編号
//第一遍dfs确定siz,fa,dep和son
void dfs1(int x,int f,int deep)//x為節點編号，f為父節點，deep為深度
{
siz[x]=1; fa[x]=f; dep[x]=deep;
int len=v[x].size(),masiz=0;//masiz為目前點x最大的的子樹大小
for(int i=0;i<len;i++)
{
int u=v[x][i];
if(u==f) continue;//如果為父節點就跳過，否則u就是兒子節點
dfs1(u,x,deep+1);//向下深搜
siz[x]+=siz[u];//siz[x]等于目前x點的子樹大小再加上兒子節點u的大小
if(siz[u]>masiz)//如果兒子節點u的子樹大小大于之前兒子節點子樹大小的最大值
{
masiz=siz[u];//更新masiz
son[x]=u;//更新重兒子
}
}
}
int top[100005],id[100005],val[100005],cnt;
//top[x]表示x所在的重鍊的頂端
//id[x]表示節點x在dfs序中的編号（線段樹需要用到）
//val[x]表示點x線上段樹中的值
//第2遍dfs确定top,id和val
void dfs2(int x,int topp)//x為節點編号，topp表示x所在的重鍊的頂端
{
id[x]=++cnt;
top[x]=topp;
val[cnt]=va[x];
if(son[x]==0) return;//如果沒有兒子直接傳回
dfs2(son[x],topp);//優先向重兒子dfs，保證重鍊編号連續
int len=v[x].size();
for(int i=0;i<len;i++)
{
int u=v[x][i];
if(u==son[x]||u==fa[x]) continue;//如果節點u是父節點或重兒子則跳過（重兒子搜過了）
dfs2(u,u);//此時u是輕兒子，輕兒子所在的重鍊以自己為開端
}
}
//線段樹
int t[400005],laz[400005];//t是線段樹的節點，laz為懶标記
//建樹
inline void build(int o,int l,int r)//o是線段樹的節點編号，l和r分别為線段樹區間的左右端點
{
if(l==r)//如果區間為一個點
{
t[o]=val[l];//更新節點值
return;//下面沒有節點了，傳回
}
//否則
int mid=l+r>>1;
//建樹
build(o*2,l,mid);
build(o*2+1,mid+1,r);
//更新節點值
t[o]=(t[o*2]+t[o*2+1])%mo;
}
//下傳懶标記
inline void push(int o,int l,int r)//o,l,r同上
{
int mid=l+r>>1;
//更新兒子的值
t[o*2]=(t[o*2]+laz[o]*(mid-l+1))%mo;
t[o*2+1]=(t[o*2+1]+laz[o]*(r-mid))%mo;
//更新兒子的懶标記的值
laz[o*2]=(laz[o*2]+laz[o])%mo;
laz[o*2+1]=(laz[o*2+1]+laz[o])%mo;
laz[o]=0;//原節點的懶标記已下傳，清零
}
//更新區間值
inline void change(int o,int l,int r,int ql,int qr,int x)
{
//o,l,r同上，ql和qr為要更新的左右端點，x為要增加的值
if(l>qr||r<ql) return;//如果目前區間與要更新的區間無關，傳回
if(l>=ql&&r<=qr)//如果目前區間在要更新的區間内部，更新
{
t[o]=(t[o]+x*(r-l+1))%mo;//更新節點值
laz[o]+=x;//更新懶标記
return;//目前區間在要更新的區間内部，不需要向下更新
}
//目前區間不完全在更新的區間内
int mid=l+r>>1;
push(o,l,r);//下傳懶标記并更新兒子的值
//嘗試更新左右兒子節點
change(o*2,l,mid,ql,qr,x);
change(o*2+1,mid+1,r,ql,qr,x);
t[o]=(t[o*2]+t[o*2+1])%mo;//更新節點值
}
//查詢區間值
inline int query(int o,int l,int r,int ql,int qr)
{
//o,l,r同上，ql和qr為要查詢的區間
if(l>qr||r<ql) return 0;//如果目前區間與要查詢的區間無關，傳回0
if(l>=ql&&r<=qr) return t[o];//如果目前區間在要查詢的區間内部
//不需要繼續向下，直接傳回目前區間的值
//目前區間不完全在更新的區間内
int mid=l+r>>1;
push(o,l,r);//下傳懶标記并更新兒子的值
int res=(query(o*2,l,mid,ql,qr)+query(o*2+1,mid+1,r,ql,qr))%mo;
t[o]=(t[o*2]+t[o*2+1])%mo;//更新節點值（之前的push函數可能會更新兒子的值）
return res;
}
//将樹從x到y結點最短路徑上所有節點的值都加上z
inline void ins1(int x,int y,int z)//x,y,z意義如上
{
while(top[x]!=top[y])//若x和y不在同一條重鍊上
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
//首先保證點x所在的重鍊頂端的深度較大才能保證最終x和y一定能“走”到同一條重鍊
change(1,1,n,id[top[x]],id[x],z);
//更新點x所在的重鍊的值
//(因為第2遍dfs後一條重鍊的編号是連續的是以可以直接将整個區間更新）
x=fa[top[x]];//這條鍊更新完了就向下一條鍊更新
}
//此時點x和點y已處于同一條重鍊
if(dep[x]>dep[y]) swap(x,y);//保證點x的深度更小
change(1,1,n,id[x],id[y],z);//剩下隻要更新id[x]到id[y]的區間就好了
}
//将以x為根節點的子樹内所有節點值都加上z
inline void ins2(int x,int z)//x,z意義同上
{
//在第2遍dfs時已經使點x的後代節點的編号（id[]）分别從id[x]+1到di[x]+siz[x]-1
//減1是因為siz[x]還包括自己
change(1,1,n,id[x],id[x]+siz[x]-1,z);//直接更新x的子樹（包括自己）
}
//求樹從x到y結點最短路徑上所有節點的值之和
inline int q1(int x,int y)//x,y意義如上
{
int res=0;//res儲存結果
//像更新操作一樣，也是用線段樹查詢一整個區間
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
res=(res+query(1,1,n,id[top[x]],id[x]))%mo;
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
res=(res+query(1,1,n,id[x],id[y]))%mo;
return res;
}
//求以x為根節點的子樹内所有節點值之和
inline int q2(int x)
{
//像更新操作一樣，也是用線段樹查詢一整個區間
return query(1,1,n,id[x],id[x]+siz[x]-1);
}
//終于來到了主程式...
int main()
{
int a,b,c;
cin>>n>>m>>roo>>mo;
for(int i=1;i<=n;i++)
scanf("%d",&va[i]),va[i]%=mo;
for(int i=1;i<n;i++)
{
scanf("%d%d",&a,&b);
v[a].push_back(b);
v[b].push_back(a);
}
dfs1(roo,0,1);//第1遍深搜
dfs2(roo,roo);//第2遍深搜
build(1,1,n);//建樹
int k;
while(m--)
{
scanf("%d",&k);
if(k==1)
{
scanf("%d%d%d",&a,&b,&c);
c%=mo;
ins1(a,b,c);
}
if(k==2)
{
scanf("%d%d",&a,&b);
printf("%d\n",q1(a,b));
}
if(k==3)
{
scanf("%d%d",&a,&b);
b%=mo;
ins2(a,b);
}
if(k==4)
{
scanf("%d",&a);
printf("%d\n",q2(a));
}
}
return 0;
}