\(n\) 个点， \(m\) 个操作数， 根结点为 \(R\)， 取模数为 \(mod\)。
输入一颗树。
支持的操作：
- 把 \(x\) 点的点权增加（或修改）\(y\)。
- 将树从 \(x\) 到 \(y\) 结点最短路径上所有节点的值都加上 \(z\)。
- 询问某个节点 \(x\) 到 \(y\) 节点的路径中所有点的点权和 (或maxn)。
- 把 \(x\) 为根结点的子树中所有点的点权都增加 \(y\)。
- 求以 \(x\) 为根节点的子树内所有节点值之和
const ll N = 3e5 + 4;
ll n, m, tot, R, mod;
ll head[N], fa[N], son[N], siz[N], top[N], dep[N], seg[N], rev[N], a[N], lim[N];
struct nodee
{
ll to, nxt;
} t[2 * N];
void add(ll x, ll y)
{
t[++tot].to = y;
t[tot].nxt = head[x];
head[x] = tot;
}
void dfs1(ll u, ll father)
{
siz[u] = 1, fa[u] = father, dep[u] = dep[father] + 1;
for (ll i = head[u]; i; i = t[i].nxt)
{
ll y = t[i].to;
if (siz[y] == 0)
{
dfs1(y, u);
siz[u] += siz[y];
if (siz[y] > siz[son[u]])
{
son[u] = y;
}
}
}
}
void dfs2(ll u)
{
seg[u] = ++seg[0];
rev[seg[0]] = u;
if (son[u])
{
top[son[u]] = top[u];
dfs2(son[u]);
}
for (ll i = head[u]; i; i = t[i].nxt)
{
ll y = t[i].to;
if (y == son[u] || fa[u] == y)
{
continue;
}
dfs2(y);
}
lim[u] = seg[0];
}
struct node
{
ll L, R, sum, tag, maxn;
node *lc, *rc;
};
void pushup(node *now)
{
now->sum = (now->lc->sum + now->rc->sum) % mod;
now->maxn = max(now->lc->maxn, now->rc->maxn);
}
inline void maketag(node *now, ll w)
{
now->tag = (now->tag + w) % mod;
now->sum = (now->sum + (now->R - now->L + 1) * w) % mod;
now->maxn = w;
}
inline void pushdown(node *now)
{
if (now->tag == 0)
return;
maketag(now->lc, now->tag);
maketag(now->rc, now->tag);
now->tag = 0;
}
void build(node *now, ll l, ll r)
{
now->L = l;
now->R = r;
now->tag = 0;
if (l < r)
{
ll mid = (l + r) >> 1;
now->lc = new node;
now->rc = new node;
build(now->lc, l, mid);
build(now->rc, mid + 1, r);
pushup(now);
}
else
{
now->maxn = a[rev[l]];
now->sum = a[rev[l]];
now->lc = now->rc = NULL;
}
}
void change(node *now, ll l, ll r, ll w)
{
if (l <= now->L and now->R <= r)
{
maketag(now, w);
}
else if (!((now->L > r) || (now->R < l)))
{
pushdown(now);
change(now->lc, l, r, w);
change(now->rc, l, r, w);
pushup(now);
}
}
ll check1(node *now, ll l, ll r)
{
if (l <= now->L and now->R <= r)
return now->sum;
if ((now->L > r) || (now->R < l))
return 0;
pushdown(now);
return (check1(now->lc, l, r) + check1(now->rc, l, r)) % mod;
}
ll check2(node *now, ll l, ll r)
{
if (l <= now->L and now->R <= r)
return now->maxn;
if ((now->L > r) || (now->R < l))
return -INF;
pushdown(now);
return max(check2(now->lc, l, r), check2(now->rc, l, r));
}
int main()
{
n = read(), m = read();
R = 1, mod = INF; // R为根结点序号
for (ll i = 1; i <= n; i++)
top[i] = i;
for (ll i = 1; i <= n; i++)
a[i] = read();
for (ll i = 1; i <= n - 1; i++)
{
ll x = read(), y = read();
add(x, y);
add(y, x);
}
dfs1(R, 0);
dfs2(R);
node *root;
root = new node;
build(root, 1, n);
for (int i = 1; i <= m; ++i)
{
ll opt = read(), x = read(), y, z;
// 把 x 点的点权增加 y
// 如果想要修改，更改上面的 maketag
if (opt == 0)
{
y = read();
change(root, seg[x], seg[x], y);
}
// 表示将树从 x 到 y 结点最短路径上所有节点的值都加上 z。
else if (opt == 1)
{
y = read(), z = read();
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]])
swap(x, y);
change(root, seg[top[x]], seg[x], z);
x = fa[top[x]];
}
if(seg[x] > seg[y]) swap(x, y);
change(root, seg[x], seg[y], z);
}
// 询问某个节点 x 到 y 节点的路径中所有点的点权和 (或maxn)
else if (opt == 2)
{
y = read();
ll sum = 0;
// ll maxn = -2147483647;
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]])
swap(x, y);
sum = (sum + check1(root, seg[top[x]], seg[x])) % mod;
// maxn = max(maxn, check2(root, seg[top[x]], seg[x]));
x = fa[top[x]];
}
if (seg[x] > seg[y])
swap(x, y);
sum = (sum + check1(root, seg[x], seg[y])) % mod;
// maxn = max(maxn, check2(root, seg[x], seg[y]));
printf("%lld\n", sum);
}
// 把 x 为根结点的子树中所有点的点权都增加 y
else if (opt == 3)
{
y = read();
change(root, seg[x], lim[x], y);
}
// 求以 x 为根节点的子树内所有节点值之和
else if (opt == 4)
{
ll ans = check1(root, seg[x], lim[x]) % mod;
printf("%lld\n", ans);
}
}
return 0;
}