P3384
不知道哪里错了QAQ
求dalao解答%%%
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define T long long
inline void swap(T &x, T &y)
{
T t = x;
x = y, y = t;
}
inline T read()
{
T num = 0; int f = 1; char c = getchar();
while (c < 48 || c > 57){ if (c == '-')f = -1; c = getchar(); }
while (c >= 48 && c <= 57)num = num * 10 + (c ^ 48), c = getchar();
return num * f;
}
#undef T
#define a QAQ
#define int long long
int as[100005], n, m, r, mod, dfn[100005], fa[100005], top[100005], hs[100005], sz[100005], dep[100005], a[100005];
#undef a
//
int addv[400005], sum[400005];
int Sn;
int GetLength(int t)
{
int p = 1;
while (p < t)p <<= 1ll;
return p;
}
inline void pushdown()
{
}
inline void build(int n)
{
Sn = GetLength(n);
for (int i = 1; i <= n; i++)
{
addv[i + Sn - 1] = QAQ[i];
}
for (int i = Sn - 1; i; i--)sum[i] = (addv[i << 1] + addv[(i << 1) ^ 1]) % mod;
}
int res;
inline void query(int u, int l, int r, int L, int R, int adds)
{
//printf("Searching... u = %d, [%d, %d], ad = %d\n", u, l, r, adds);
if (L <= l&&r <= R){ res += sum[u] + ((addv[u] + adds) * (r - l + 1)); res %= mod; return; }
else
{
int M = l + (r - l) / 2;
if (L <= M)query(u << 1, l, M, L, R, (adds + addv[u]) % mod);
if (R > M)query((u << 1) ^ 1, M + 1, r, L, R, (adds + addv[u]) % mod);
}
}
#define min(a,b) (a>b?b:a)
#define max(a,b) (a<b?b:a)
inline void update(int u, int l, int r, int L, int R, int k){
if (L <= l&&r <= R)
{
addv[u] += k;
addv[u] %= mod;
}
else
{
int mid = l + (r - l) / 2;
if (L <= mid)update(u<<1,l,mid, L, R, k);
if (R>mid)update((u << 1) ^ 1, mid+1, r, L, R, k);
sum[u] = (sum[u] + k*(1+min(r, R) - max(l, L))) % mod;
}
}
struct Edge{
int v, nxt;
}e[100005 << 1];
int h[100005], cnt = 1;
inline void addedge(int u, int v)
{
e[cnt] = { v, h[u] };
h[u] = cnt++;
}
int dfs1(int u, int fat, int dept)
{
sz[u] = 1, fa[u] = fat, dep[u] = dept;
int tmp = 0;
for (int i = h[u]; i; i = e[i].nxt)
{
if (e[i].v == fat)continue;
dfs1(e[i].v, u, dept + 1);
sz[u] += sz[e[i].v];
if (sz[e[i].v] > tmp)tmp = sz[e[i].v], hs[u] = e[i].v;
}
return 0;
}
int cn;
int dfs2(int u, int t)
{
dfn[u] = ++cn;
QAQ[cn] = as[u];
top[u] = t;
if (!hs[u])return 0;
dfs2(hs[u], t);
for (int i = h[u]; i; i = e[i].nxt)
{
if (e[i].v == fa[u] || e[i].v == hs[u])continue;
dfs2(e[i].v, e[i].v);
}
return 0;
}
signed main()
{
//freopen("C:\\Users\\Administrator\\Downloads\\P3384_2.in", "r", stdin);
int n = read(), m = read(), r = read(); mod = read();
for (int i = 1; i <= n; i++)as[i] = read()%mod;
for (int i = 1; i < n; i++)
{
int x = read(), y = read();
addedge(x, y); addedge(y, x);
}
dfs1(r, -1, 1);
dfs2(r, r);
build(n);
while (m--)
{
int op = read();
if (op == 2)
{
int x = read(), y = read();
int ans = 0;
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]])swap(x,y);
res = 0;
query(1, 1, Sn, dfn[top[x]], dfn[x], 0);
ans = (ans+res)%mod;
x = fa[x];
}
if (dep[x] > dep[y])swap(x, y);
res = 0;
query(1, 1, Sn, dfn[x], dfn[y], 0);
printf("%d\n", (ans + res) % mod);
}
else if (op == 1)
{
int x = read(), y = read(), z = read();
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]])swap(x, y);
update(1, 1, Sn, dfn[top[x]], dfn[x], z);
x = fa[x];
}
if (dep[x] > dep[y])swap(x, y);
update(1,1,Sn,dfn[x], dfn[y], z);
}
else if (op == 3)
{
int x = read(), z = read();
update(1,1,Sn,dfn[x], dfn[x] + sz[x] - 1, z);
}
else
{
int x = read();
res = 0;
query(1, 1, Sn, dfn[x], dfn[x] + sz[x] - 1, 0);
printf("%d\n", res%mod);
}
}
getchar();
return 0;
}