树剖啥的自己调吧……
by Smile_Cindy @ 2020-10-04 20:30:33
写个generator啥的对拍都行
std
```cpp
#include <bits/stdc++.h>
#define endl '\n'
#define lson (rt<<1)
#define rson (rt<<1|1)
using namespace std;
const int MAX_N=100005;
int n,m,root,Mod;
int A[MAX_N];
vector<int> g[MAX_N];
int DFN[MAX_N],siz[MAX_N],top[MAX_N],idx,fa[MAX_N],dep[MAX_N];
void dfs(int v,int last)
{
fa[v]=last;
dep[v]=dep[last]+1;
siz[v]=1;
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i];
if(to==last)continue;
dfs(to,v);
siz[v]+=siz[to];
}
}
void DFS(int v,int bel)
{
DFN[v]=++idx;
top[v]=bel;
int ch=0;
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i];
if(to==fa[v])continue;
if(siz[to]>siz[ch])ch=to;
}
if(ch)DFS(ch,bel);
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i];
if(to==fa[v])continue;
if(to!=ch)DFS(to,to);
}
}
int add(int a,int b)
{
return a+b>=Mod?a+b-Mod:a+b;
}
int mul(int a,int b)
{
return 1ll*a*b%Mod;
}
int sum[MAX_N<<2],tag[MAX_N<<2];
void pushup(int rt)
{
sum[rt]=add(sum[lson],sum[rson]);
}
void operate(int rt,int l,int r,int x)
{
sum[rt]=add(sum[rt],mul(x,r-l+1));
tag[rt]=add(tag[rt],x);
}
void pushdown(int rt,int l,int r)
{
if(tag[rt])
{
int mid=(l+r)/2;
operate(lson,l,mid,tag[rt]);
operate(rson,mid+1,r,tag[rt]);
tag[rt]=0;
}
}
int query(int rt,int l,int r,int ql,int qr)
{
if(ql==l && qr==r)return sum[rt];
pushdown(rt,l,r);
int mid=(l+r)/2;
if(qr<=mid)return query(lson,l,mid,ql,qr);
else if(ql>mid)return query(rson,mid+1,r,ql,qr);
else return add(query(lson,l,mid,ql,mid),query(rson,mid+1,r,mid+1,qr));
}
void modify(int rt,int l,int r,int ql,int qr,int x)
{
if(l==ql && r==qr)
{
operate(rt,l,r,x);
return;
}
pushdown(rt,l,r);
int mid=(l+r)/2;
if(qr<=mid)modify(lson,l,mid,ql,qr,x);
else if(ql>mid)modify(rson,mid+1,r,ql,qr,x);
else
{
modify(lson,l,mid,ql,mid,x);
modify(rson,mid+1,r,mid+1,qr,x);
}
pushup(rt);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>root>>Mod;
for(int i=1;i<=n;i++)cin>>A[i];
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(root,0);
DFS(root,root);
for(int i=1;i<=n;i++)modify(1,1,n,DFN[i],DFN[i],A[i]);
while(m--)
{
int op;
cin>>op;
if(op==1)
{
int x,y,z;
cin>>x>>y>>z;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
modify(1,1,n,DFN[top[x]],DFN[x],z);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
modify(1,1,n,DFN[x],DFN[y],z);
}
else if(op==2)
{
int x,y;
cin>>x>>y;
int ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans=add(ans,query(1,1,n,DFN[top[x]],DFN[x]));
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
ans=add(ans,query(1,1,n,DFN[x],DFN[y]));
cout<<ans<<endl;
}
else if(op==3)
{
int x,y;
cin>>x>>y;
modify(1,1,n,DFN[x],DFN[x]+siz[x]-1,y);
}
else
{
int x;
cin>>x;
cout<<query(1,1,n,DFN[x],DFN[x]+siz[x]-1)<<endl;
}
}
return 0;
}
```
by Smile_Cindy @ 2020-10-04 20:31:24