# 求大佬看看树链剖分模板哪里错了

@大雾山上 2019-05-15 22:52 回复
#include<bits/stdc++.h>
using namespace std;
const int M=1000001;
long long n,m,k,tot,cnt,MOD,a[M];
int son[M],seg[M],rev[M],top[M];
struct Edge
{
int next,to;
}edge[1000001];
struct Tree
{
int l,r;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define sum(x) tree[x].sum
}tree[4000001];
{
edge[tot].to=to;
}
void build(int p,int l,int r)
{
l(p)=l;
r(p)=r;
if(l==r)
{
sum(p)=a[rev[l]];
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
sum(p)=sum(p*2)+sum(p*2+1);
}
{
{
}
}
void change(int l,int r,int p,int d)
{
if(l<=l(p)&&r>=r(p))
{
sum(p)+=d*(r(p)-l(p)+1);
return;
}
int mid=(l(p)+r(p))/2;
if(l<=mid) change(p*2,l,r,d);
if(r>mid) change(p*2+1,l,r,d);
sum(p)=sum(p*2)+sum(p*2+1);
}
long long ask(int l,int r,int p)
{
if(l<=l(p)&&r>=r(p)) return sum(p);
int mid=(l(p)+r(p))/2;
long long ans=0;
return ans%MOD;
}
void dfs1(int u,int f)
{
dep[u]=dep[f]+1;
fa[u]=f;
size[u]=1;
{
int v=edge[i].to;
if(v!=f)
{
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[son[u]])
son[u]=v;
}
}
}
void dfs2(int u,int f)
{
if(son[u])
{
seg[son[u]]=++cnt;
rev[cnt]=son[u];
top[son[u]]=top[u];
dfs2(son[u],u);
}
{
int v=edge[i].to;
if(!top[v])
{
seg[v]=++cnt;
rev[cnt]=v;
top[v]=v;
dfs2(v,u);
}
}
}
void get_init(int x,int y,int d)
{
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(dep[fx]<dep[fy])
{
swap(fx,fy);
swap(x,y);
}
change(cnt,seg[fx],seg[fy],d);
x=fa[x];
fx=top[x];
}
if(dep[x]>dep[y])
swap(x,y);
change(cnt,seg[x],seg[y],d);
return;
}
int get_sum(int x,int y)
{
int ans=0;
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(dep[fx]<dep[fy])
{
swap(fx,fy);
swap(x,y);
}
x=fa[x];
fx=top[x];
}
if(dep[x]>dep[y])
swap(x,y);
return ans%MOD;
}
int main()
{
cin>>n>>m>>k>>MOD;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n-1;i++)
{
int x,y;
cin>>x>>y;
}
dfs1(k,k);
cnt=seg[1]=top[1]=rev[1]=1;
dfs2(k,k);
build(1,1,cnt);
for(int i=1;i<=m;i++)
{
int op;
cin>>op;
if(op==1)
{
int x,y,z;
cin>>x>>y>>z;
get_init(x,y,z);
}
if(op==2)
{
int x,y;
cin>>x>>y;
cout<<get_sum(x,y)<<endl;
}
if(op==3)
{
int x,y;
cin>>x>>y;
change(1,seg[x],seg[x]+size[x]-1,y);
}
if(op==4)
{
int x;
cin>>x;
}