#include<bits/stdc++.h>
using namespace std;
int n, m, R, P;
int w[1000010], h[1000010], e[1000010], ne[1000010], idx;
int id[1000010], nw[1000010], cnt;
int dep[1000010], sz[1000010], top[1000010], fa[1000010], son[1000010];
struct node{
int l, r;
long long add, sum;
} tr[1000010];
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs1(int u, int father, int depth){
dep[u] = depth, fa[u] = father, sz[u] = 1;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == father) continue;
dfs1(j, u, depth+1);
sz[u] += sz[j];
if(sz[son[u]] < sz[j]) son[u] = j;
}
}
void dfs2(int u, int t){
id[u] = ++cnt, nw[cnt] = w[u], top[u] = t;
if(!son[u]) return ;
dfs2(son[u], t);
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == fa[u] || j == son[u]) continue;
dfs2(j, j);
}
}
void pushup(int u){
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u){
auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
if(root.add){
left.add += root.add, left.sum += root.add * (left.r - left.l + 1);
right.add += root.add, right.sum += root.add * (right.r - right.l + 1);
root.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(u << 1, l, mid);
build(u << 1 | 1, mid+1, r);
pushup(u);
}
void update(int u, int l, int r, int k){
if(l <= tr[u].l && r >= tr[u].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(u << 1, l, r, k);
if(r > mid) update(u << 1 | 1, l, r, k);
pushup(u);
}
long long query(int u, int l, int r){
if(l <= tr[u].l && r >= tr[u].r){
return tr[u].sum;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
long long res = 0;
if(l <= mid) res += query(u << 1, l, r);
if(r > mid) res += query(u << 1 | 1, l, r);
return res;
}
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);
}
long long query_path(int u, int v){
long long 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;
}
long long query_tree(int u){
return query(1, id[u], id[u] + sz[u] - 1);
}
int main(){
scanf("%d%d%d%d", &n, &m, &R, &P);
for(int i = 1; i <= n; i++){
scanf("%d", &w[i]);
}
memset(h, -1, sizeof(h));
for(int i = 0; i < n-1; i++){
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
dfs1(R, -1, 1);
dfs2(R, -1);
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("%lld\n", query_path(u, v) % P);
}else{
printf("%lld\n", query_tree(u) % P);
}
}
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Testcase #1 | 358.53 us | 3 MB + 968 KB | Runtime Error | Score: 0 | 显示更多 |