树链剖分模板,当然是轻重链剖分。
我用带懒惰标记的线段树。
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
ll vet[200005], head[100005], nxt[200005], num, cost[100005], numa,
deep[100005], fa[100005], size[100005], top[100005], tree[400005],
tag[400005], pos[100005], a[100005], son[100005], q, n, m, R, P, x, y, z;
void add(ll u, ll v){
num ++;
vet[num] = v;
nxt[num] = head[u];
head[u] = num;
}
void dfs(ll u, ll fat, ll dep){
deep[u] = dep;
fa[u] = fat;
size[u] = 1;
ll maxson = 0, sonn = 0;
for(int i = head[u]; i; i = nxt[i]){
ll v = vet[i];
if(v == fat) continue;
dfs(v, u, dep+1);
size[u] += size[v];
if(size[v] > maxson){
maxson = size[v];
sonn = v;
}
}
son[u] = sonn;
}
void DFS(ll u, ll fat, ll number){
top[u] = number;
numa ++;
a[numa] = cost[u];
pos[u] = numa;
if(son[u] == 0) return;
DFS(son[u], u, number);
for(int i = head[u]; i; i = nxt[i]){
ll v = vet[i];
if(v == fat || v == son[u]) continue;
DFS(v, u, v);
}
}
void maketree(ll p, ll l, ll r){
if(l == r){
tree[p] = a[l] % P;
return;
}
ll mid = l + (r-l)/2;
maketree(p+p, l, mid);
maketree(p+p+1, mid+1, r);
tree[p] = tree[p+p] + tree[p+p+1];
tree[p] %= P;
}
void pushdown(ll p, ll l, ll r){
ll mid = l + (r-l)/2;
if(tag[p] > 0 && l != r){
tree[p+p] += (mid - l + 1) * tag[p] % P; tag[p+p] += tag[p] % P;
tree[p+p+1] += (r - mid) * tag[p] % P; tag[p+p+1] += tag[p] % P;
tag[p+p] %= P; tag[p+p+1] %= P;
tag[p] = 0;
}
}
void add(ll p, ll l, ll r, ll x, ll y, ll z){
pushdown(p, l, r);
if(l == x && r == y){
tree[p] += (r-l+1) * z % P;
tag[p] += z % P;
return;
}
ll mid = l + (r-l)/2;
if(x > mid) add(p+p+1, mid+1, r, x, y, z);
else if(y <= mid) add(p+p, l, mid, x, y, z);
else {
add(p+p, l, mid, x, mid, z);
add(p+p+1, mid+1, r, mid+1, y, z);
}
tree[p] = tree[p+p] + tree[p+p+1];
tree[p] %= P;
}
ll acc(ll p, ll l, ll r, ll x, ll y){
pushdown(p, l, r);
if(l == x && r == y){
tree[p] %= P;
return tree[p] % P;
}
ll mid = l + (r-l)/2;
if(x > mid) return acc(p+p+1, mid+1, r, x, y);
else if(y <= mid) return acc(p+p, l, mid, x, y);
else return acc(p+p, l, mid, x, mid) + acc(p+p+1, mid+1, r, mid+1, y);
}
void change(ll u, ll v, ll c){
c %= P;
while(top[u] != top[v]){
if(deep[top[u]] < deep[top[v]]) swap(u, v);
add(1, 1, n, pos[top[u]], pos[u], c);
u = fa[top[u]];
}
if(deep[u] < deep[v]) swap(u, v);
add(1, 1, n, pos[v], pos[u], c);
}
ll find(ll u, ll v){
ll an = 0;
while(top[u] != top[v]){
if(deep[top[u]] < deep[top[v]]) swap(u, v);
an += acc(1, 1, n, pos[top[u]], pos[u]);
an %= P;
u = fa[top[u]];
}
if(deep[u] < deep[v]) swap(u, v);
an += acc(1, 1, n, pos[v], pos[u]);
return an % P;
}
int main(){
scanf("%lld%lld%lld%lld", &n, &m, &R, &P);
for(int i = 1; i <= n; i++){
scanf("%lld", &cost[i]);
cost[i] = cost[i] % P;
}
for(int i = 1; i < n; i++){
scanf("%lld%lld", &x, &y);
add(x, y);
add(y, x);
}
dfs(R, 0, 1);
DFS(R, 0, R);
// for(int i = 1; i <= n; i++)
// printf("%lld ", top[i]);
maketree(1, 1, n);
for(int i = 1; i <= m; i++){
scanf("%lld", &q);
if(q == 1){
scanf("%lld%lld%lld", &x, &y, &z);
change(x, y, z % P);
}else if(q == 2){
scanf("%lld%lld", &x, &y);
printf("%lld\n", find(x, y));
}else if(q == 3){
scanf("%lld%lld", &x, &z);
add(1, 1, n, pos[x], pos[x] + size[x] - 1, z % P);
}else{
scanf("%lld", &x);
printf("%lld\n", acc(1, 1, n, pos[x], pos[x] + size[x] - 1));
}
}
return 0;
}