已知一棵包含 NN 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：

  • 1 x y z，表示将树从 xx 到 yy 结点最短路径上所有节点的值都加上 zz。

  • 2 x y，表示求树从 xx 到 yy 结点最短路径上所有节点的值之和。

  • 3 x z，表示将以 xx 为根节点的子树内所有节点值都加上 zz。

  • 4 x 表示求以 xx 为根节点的子树内所有节点值之和

输入格式

第一行包含 44 个正整数 N,M,R,PN,M,R,P，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。

接下来一行包含 NN 个非负整数，分别依次表示各个节点上初始的数值。

接下来 N−1N-1 行每行包含两个整数 x,yx,y，表示点 xx 和点 yy 之间连有一条边（保证无环且连通）。

接下来 MM 行每行包含若干个正整数，每行表示一个操作。

输出格式

输出包含若干行，分别依次表示每个操作 22 或操作 44 所得的结果（对 PP 取模）。

对于 100%100\% 的数据： 1≤N≤1051\le N \leq {10}^5，1≤M≤1051\le M \leq {10}^5，1≤R≤N1\le R\le N，1≤P≤231−11\le P \le 2^{31}-1。所有输入的数均在 int 范围内。
#时间复杂度O（m logn logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#define LL long long
#define lc u<<1
#define rc u<<1|1
const int N=100010;
int n,m,a,b,root,P,w[N];
vector<int> e[N];
int fa[N],dep[N],sz[N],son[N];
int top[N],id[N],nw[N],cnt; //重链
struct tree{
  int l,r; 
  LL add,sum;
}tr[N*4]; //线段树

void dfs1(int u,int father){//搞fa,dep,sz,son
  fa[u]=father,dep[u]=dep[father]+1,sz[u]=1;
  for(int v:e[u]){
    if(v==father) continue;
    dfs1(v,u);
    sz[u]+=sz[v];
    if(sz[son[u]]<sz[v]) son[u]=v; 
  }
}
void dfs2(int u,int t){ //搞top,id,nw
  top[u]=t,id[u]=++cnt,nw[cnt]=w[u];
  if(!son[u]) return;
  dfs2(son[u],t);
  for(int v:e[u]){
    if(v==fa[u]||v==son[u])continue;
    dfs2(v,v);
  }
}
void pushup(int u){
  tr[u].sum=tr[lc].sum+tr[rc].sum;
}
void pushdown(int u){
  if(tr[u].add){
    tr[lc].sum+=tr[u].add*(tr[lc].r-tr[lc].l+1);
    tr[rc].sum+=tr[u].add*(tr[rc].r-tr[rc].l+1);
    tr[lc].add+=tr[u].add;
    tr[rc].add+=tr[u].add;
    tr[u].add=0;
  }
}
void build(int u,int l,int r){ //构建线段树
  tr[u]={l,r,0,nw[r]};
  if(l==r) return;
  int mid=l+r>>1;
  build(lc,l,mid),build(rc,mid+1,r);
  pushup(u);
}
LL query(int u,int l,int r){ //线段树查询
  if(l<=tr[u].l&&tr[u].r<=r)return tr[u].sum;
  pushdown(u);
  int mid=tr[u].l+tr[u].r>>1;
  LL res=0;
  if(l<=mid) res+=query(lc,l,r);
  if(r>mid) res+=query(rc,l,r);
  return res;
}
LL query_path(int u,int v){ //查询路径
  LL res=0;
  while(top[u]!=top[v]){
    if(dep[top[u]]<dep[top[v]]) swap(u,v);
    res+=query(1,id[top[u]],id[u]);
    u=fa[top[u]];
  }
  if(dep[u]<dep[v]) swap(u,v);
  res+=query(1,id[v],id[u]); //最后一段
  return res;
}
LL query_tree(int u){ //查询子树
  return query(1,id[u],id[u]+sz[u]-1);
}
void update(int u,int l,int r,int k){ //线段树修改
  if(l<=tr[u].l&&tr[u].r<=r){
    tr[u].add+=k;
    tr[u].sum+=k*(tr[u].r-tr[u].l+1);
    return;
  }
  pushdown(u);
  int mid=tr[u].l+tr[u].r>>1;
  if(l<=mid) update(lc,l,r,k);
  if(r>mid) update(rc,l,r,k);
  pushup(u);
}
void update_path(int u,int v,int k){ //修改路径
  while(top[u]!=top[v]){
    if(dep[top[u]]<dep[top[v]]) swap(u,v);
    update(1,id[top[u]],id[u],k);
    u=fa[top[u]];
  }
  if(dep[u]<dep[v]) swap(u,v);
  update(1,id[v],id[u],k); //最后一段
}
void update_tree(int u,int k){ //修改子树
  update(1,id[u],id[u]+sz[u]-1,k);
}
int main(){
  scanf("%d%d%d%d",&n,&m,&root,&P);
  for(int i=1; i<=n; i++) scanf("%d",&w[i]);
  for(int i=0; i<n-1; i++){
    scanf("%d%d",&a,&b);
    e[a].push_back(b); e[b].push_back(a);
  }
  dfs1(root,0);
  dfs2(root,root); //把树拆成链
  build(1,1,n);  //用链建线段树
  while(m--){
    int t,u,v,k; scanf("%d%d",&t,&u);
    if(t==1){
      scanf("%d%d",&v,&k);
      update_path(u,v,k);
    }
    else if(t==3){
      scanf("%d",&k);
      update_tree(u,k);
    }
    else if(t==2){
      scanf("%d",&v);
      printf("%d\n",query_path(u,v)%P);
    }
    else printf("%d\n",query_tree(u)%P);
  }
}