#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 100005
using namespace std;
struct Edge{
int to,next;
}edges[N];
struct LineTree{
int l,r;
long long sum,lazy;
}Tree[N<<2];
int cnt,head[N];
void add(int x,int y){
edges[++cnt]=Edge{y,head[x]};
head[x]=cnt;
}
int n,m,r,p,num[N];
long long ans;
int father[N],son[N],size[N],top[N],seg[N],rev[N],d[N];
void pushdown(int x){
Tree[x<<1].sum+=Tree[x].lazy*(Tree[x<<1].r-Tree[x<<1].l+1);
Tree[x<<1].lazy+=Tree[x].lazy;
Tree[x<<1|1].sum+=Tree[x].lazy*(Tree[x<<1|1].r-Tree[x<<1|1].l+1);
Tree[x<<1|1].lazy+=Tree[x].lazy;
Tree[x<<1].sum%=p;
Tree[x<<1].lazy%=p;
Tree[x<<1|1].sum%=p;
Tree[x<<1|1].lazy%=p;
Tree[x].lazy=0;
return;
}
void pushup(int x){
Tree[x].sum=Tree[x<<1].sum+Tree[x<<1|1].sum;
Tree[x].sum%=p;
return;
}
void build(int x,int l,int r){
Tree[x].l=l,Tree[x].r=r;
if(l==r){
Tree[x].sum=num[rev[l]];
Tree[x].sum%=p;
return;
}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
pushup(x);
return;
}
void add(int x,int l,int r,int ad){
if(Tree[x].l>r||Tree[x].r<l)return;
if(Tree[x].l>=l&&Tree[x].r<=r){
Tree[x].sum+=(Tree[x].r-Tree[x].l+1)*ad;
Tree[x].lazy+=ad;
Tree[x].sum%=p;
Tree[x].lazy%=p;
return;
}
if(Tree[x].lazy)pushdown(x);
int mid=(Tree[x].l+Tree[x].r)>>1;
add(x<<1,l,r,ad);
add(x<<1|1,l,r,ad);
pushup(x);
return;
}
void query(int x,int l,int r){
if(Tree[x].l>r||Tree[x].r<l)return;
if(Tree[x].l>=l&&Tree[x].r<=r){
ans+=Tree[x].sum;
ans%=p;
return;
}
if(Tree[x].lazy)pushdown(x);
int mid=(Tree[x].l+Tree[x].r)>>1;
query(x<<1,l,r);
query(x<<1|1,l,r);
}
void dfs1(int x,int fa){
father[x]=fa,size[x]=1,d[x]=d[fa]+1;
for(int i=head[x];i;i=edges[i].next){
int v=edges[i].to;
if(v!=fa){
dfs1(v,x);
size[x]+=size[v];
if(size[v]>size[son[x]])
son[x]=v;
}
}
}
void dfs2(int x,int fa){
int e,v;
if(son[x]){
seg[son[x]]=++seg[0];
top[son[x]]=top[x];
rev[seg[0]]=son[x];
dfs2(son[x],x);
}
for(int i=head[x];i;i=edges[i].next){
v=edges[i].to;
if(!top[v]){
seg[v]=++seg[0];
rev[seg[0]]=v;
top[v]=v;
dfs2(v,x);
}
}
}
void ask(int x,int y){
ans=0;
int fx=top[x],fy=top[y];
while(fx!=fy){
if(d[fx]<d[fy]){
swap(fx,fy);
swap(x,y);
}
query(1,seg[fx],seg[x]);
x=father[fx],fx=top[x];
}
if(d[x]>d[y])swap(x,y);
query(1,seg[x],seg[y]);
printf("%lld\n",ans%p);
}
void _add(int x,int y,int z){
int fx=top[x],fy=top[y];
while(fx!=fy){
if(d[fx]<d[fy]){
swap(fx,fy);
swap(x,y);
}
add(1,seg[fx],seg[x],z);
x=father[fx],fx=top[x];
}
if(d[x]>d[y])swap(x,y);
add(1,seg[x],seg[y],z);
}
int main(){
scanf("%d%d%d%d",&n,&m,&r,&p);
for(int i=1;i<=n;i++)
scanf("%d",&num[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);
rev[1]=top[r]=r;
seg[0]=1,seg[r]=1;
dfs2(r,0);
build(1,1,n);
for(int i=1;i<=m;i++){
int s,x,y,z;
scanf("%d",&s);
if(s==1){
scanf("%d%d%d",&x,&y,&z);
_add(x,y,z%p);
}
else if(s==2){
scanf("%d%d",&x,&y);
ask(x,y);
}
else if(s==3){
scanf("%d%d",&x,&z);
add(1,seg[x],seg[x]+size[x]-1,z%p);
}
else if(s==4){
ans=0;
scanf("%d",&x);
query(1,seg[x],seg[x]+size[x]-1);
printf("%lld\n",ans%p);
}
}
}
by jiangby @ 2018-07-16 10:56:04
```
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 100005
using namespace std;
struct Edge{
int to,next;
}edges[N];
struct LineTree{
int l,r;
long long sum,lazy;
}Tree[N<<2];
int cnt,head[N];
void add(int x,int y){
edges[++cnt]=Edge{y,head[x]};
head[x]=cnt;
}
int n,m,r,p,num[N];
long long ans;
int father[N],son[N],size[N],top[N],seg[N],rev[N],d[N];
void pushdown(int x){
Tree[x<<1].sum+=Tree[x].lazy*(Tree[x<<1].r-Tree[x<<1].l+1);
Tree[x<<1].lazy+=Tree[x].lazy;
Tree[x<<1|1].sum+=Tree[x].lazy*(Tree[x<<1|1].r-Tree[x<<1|1].l+1);
Tree[x<<1|1].lazy+=Tree[x].lazy;
Tree[x<<1].sum%=p;
Tree[x<<1].lazy%=p;
Tree[x<<1|1].sum%=p;
Tree[x<<1|1].lazy%=p;
Tree[x].lazy=0;
return;
}
void pushup(int x){
Tree[x].sum=Tree[x<<1].sum+Tree[x<<1|1].sum;
Tree[x].sum%=p;
return;
}
void build(int x,int l,int r){
Tree[x].l=l,Tree[x].r=r;
if(l==r){
Tree[x].sum=num[rev[l]];
Tree[x].sum%=p;
return;
}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
pushup(x);
return;
}
void add(int x,int l,int r,int ad){
if(Tree[x].l>r||Tree[x].r<l)return;
if(Tree[x].l>=l&&Tree[x].r<=r){
Tree[x].sum+=(Tree[x].r-Tree[x].l+1)*ad;
Tree[x].lazy+=ad;
Tree[x].sum%=p;
Tree[x].lazy%=p;
return;
}
if(Tree[x].lazy)pushdown(x);
int mid=(Tree[x].l+Tree[x].r)>>1;
add(x<<1,l,r,ad);
add(x<<1|1,l,r,ad);
pushup(x);
return;
}
void query(int x,int l,int r){
if(Tree[x].l>r||Tree[x].r<l)return;
if(Tree[x].l>=l&&Tree[x].r<=r){
ans+=Tree[x].sum;
ans%=p;
return;
}
if(Tree[x].lazy)pushdown(x);
int mid=(Tree[x].l+Tree[x].r)>>1;
query(x<<1,l,r);
query(x<<1|1,l,r);
}
void dfs1(int x,int fa){
father[x]=fa,size[x]=1,d[x]=d[fa]+1;
for(int i=head[x];i;i=edges[i].next){
int v=edges[i].to;
if(v!=fa){
dfs1(v,x);
size[x]+=size[v];
if(size[v]>size[son[x]])
son[x]=v;
}
}
}
void dfs2(int x,int fa){
int e,v;
if(son[x]){
seg[son[x]]=++seg[0];
top[son[x]]=top[x];
rev[seg[0]]=son[x];
dfs2(son[x],x);
}
for(int i=head[x];i;i=edges[i].next){
v=edges[i].to;
if(!top[v]){
seg[v]=++seg[0];
rev[seg[0]]=v;
top[v]=v;
dfs2(v,x);
}
}
}
void ask(int x,int y){
ans=0;
int fx=top[x],fy=top[y];
while(fx!=fy){
if(d[fx]<d[fy]){
swap(fx,fy);
swap(x,y);
}
query(1,seg[fx],seg[x]);
x=father[fx],fx=top[x];
}
if(d[x]>d[y])swap(x,y);
query(1,seg[x],seg[y]);
printf("%lld\n",ans%p);
}
void _add(int x,int y,int z){
int fx=top[x],fy=top[y];
while(fx!=fy){
if(d[fx]<d[fy]){
swap(fx,fy);
swap(x,y);
}
add(1,seg[fx],seg[x],z);
x=father[fx],fx=top[x];
}
if(d[x]>d[y])swap(x,y);
add(1,seg[x],seg[y],z);
}
int main(){
scanf("%d%d%d%d",&n,&m,&r,&p);
for(int i=1;i<=n;i++)
scanf("%d",&num[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);
rev[1]=top[r]=r;
seg[0]=1,seg[r]=1;
dfs2(r,0);
build(1,1,n);
for(int i=1;i<=m;i++){
int s,x,y,z;
scanf("%d",&s);
if(s==1){
scanf("%d%d%d",&x,&y,&z);
_add(x,y,z%p);
}
else if(s==2){
scanf("%d%d",&x,&y);
ask(x,y);
}
else if(s==3){
scanf("%d%d",&x,&z);
add(1,seg[x],seg[x]+size[x]-1,z%p);
}
else if(s==4){
ans=0;
scanf("%d",&x);
query(1,seg[x],seg[x]+size[x]-1);
printf("%lld\n",ans%p);
}
}
}
```
by jiangby @ 2018-07-16 11:04:16