az
众所周知调试树剖是个重活
by WanderingTrader @ 2021-08-03 18:56:15
@[_TLEer_的小号](/user/362101) 重写一遍。这比调代码简单多了。
by lsw1 @ 2021-08-03 20:33:33
调完了，原因是取模次数不够。
我把线段树里取模和询问时取模都加上就过了。
带 `//`的是我改动的地方。
```cpp
#include <iostream>
#include <cstdio>
#include <cctype>
#define int long long
#define il inline
#define N 100010
#define re register
using namespace std;
int MOD, root;
inline int read()
{
char c;
int t = 1, ans;
while (!isdigit(c = getchar()))
if (c == '-')
t = -t;
ans = c - '0';
while (isdigit(c = getchar()))
ans = ans * 10 + c - '0';
return ans;
}
struct ln
{
int u, v, nxt;
} a[N * 5];
int n, m, p, x, y, z, k, hd[N], ar[N], tmp, op, lnsz, dep[N], f[N], tr[N], son[N], arr[N], nw[N], t[N], tot;
struct Segment_Tree
{
int L[N * 10], R[N * 10], lazy_tag[N * 10], tag[N * 10], ans[N * 10], lson[N * 10], rson[N * 10];
il void pushdown(int i)
{
lazy_tag[lson[i]] += lazy_tag[i];
ans[lson[i]] += lazy_tag[i] * (R[lson[i]] - L[lson[i]] + 1);
ans[lson[i]] %= MOD; //
lazy_tag[rson[i]] += lazy_tag[i];
ans[rson[i]] += lazy_tag[i] * (R[rson[i]] - L[rson[i]] + 1);
ans[rson[i]] %= MOD; //
lazy_tag[i] = 0;
}
il void pushup(int i)
{
ans[i] = ans[rson[i]] + ans[lson[i]];
}
il void add(int i, int l, int r, int c)
{
if (l == L[i] && R[i] == r)
{
if (l != r)
lazy_tag[i] += c;
ans[i] += c * (R[i] - L[i] + 1);
return;
}
if (r <= R[lson[i]])
add(lson[i], l, r, c);
else if (l >= L[rson[i]])
add(rson[i], l, r, c);
else
add(rson[i], L[rson[i]], r, c), add(lson[i], l, R[lson[i]], c);
pushdown(i);
pushup(i);
}
il int ask(int i, int l, int r)
{
if (l == L[i] && R[i] == r)
return ans[i];
if (lazy_tag[i])
pushdown(i);
if (r <= R[lson[i]])
return ask(lson[i], l, r) % MOD; //
if (l >= L[rson[i]])
return ask(rson[i], l, r) % MOD; //
return (ask(rson[i], L[rson[i]], r) + ask(lson[i], l, R[lson[i]])) % MOD; //
}
il void make_tree(int i, int l, int r)
{
tag[i] = i;
L[i] = l;
R[i] = r;
lson[i] = tag[i] * 2;
rson[i] = lson[i] + 1;
if (l == r)
return;
make_tree(i * 2, l, l + ((r - l) >> 1));
make_tree(i * 2 + 1, ((r - l) >> 1) + 1 + l, r);
}
} T;
void merge(int u, int v)
{
a[++lnsz].u = u;
a[lnsz].v = v;
a[lnsz].nxt = hd[u];
hd[u] = lnsz;
}
void dfs1(int u, int d, int fa)
{
int tmp = -1;
dep[u] = d;
f[u] = fa;
tr[u] = 1;
for (re int i = hd[u]; i; i = a[i].nxt)
{
if (a[i].v == fa)
continue;
dfs1(a[i].v, d + 1, u);
tr[u] += tr[a[i].v];
if (tr[a[i].v] > tmp)
tmp = tr[a[i].v], son[u] = a[i].v;
}
}
il void dfs2(int u, int tp, int fa)
{
t[u] = tp;
nw[u] = ++tot;
arr[tot] = ar[u];
if (!son[u])
return;
dfs2(son[u], tp, u);
for (re int i = hd[u]; i; i = a[i].nxt)
if (a[i].v != fa && a[i].v != son[u])
dfs2(a[i].v, a[i].v, u);
}
void dfs_add(int x, int y, int c)
{
while (t[x] != t[y])
{
if (dep[t[x]] < dep[t[y]])
swap(x, y);
T.add(1, nw[t[x]], nw[x], c);
x = f[t[x]];
}
if (dep[x] > dep[y])
swap(x, y);
T.add(1, nw[x], nw[y], c);
}
il int dfs_ask(int x, int y)
{
int ans = 0;
while (t[x] != t[y])
{
if (dep[t[x]] < dep[t[y]])
swap(x, y);
ans += T.ask(1, nw[t[x]], nw[x]);
ans %= MOD;
x = f[t[x]];
}
if (dep[x] > dep[y])
swap(x, y);
return (ans + T.ask(1, nw[x], nw[y])) % MOD;
}
signed main()
{
n = read();
m = read();
root = read();
MOD = read();
T.make_tree(1, 1, n);
for (re int i = 1; i <= n; i++)
cin >> ar[i];
for (re int i = 1; i < n; i++)
{
x = read();
y = read();
merge(x, y);
merge(y, x);
}
dfs1(root, 1, 0);
dfs2(root, root, 0);
for (re int i = 1; i <= n; i++)
T.add(1, i, i, arr[i]);
for (re int i = 0; i < m; i++)
{
op = read();
x = read();
if (op == 1)
{
y = read();
z = read();
dfs_add(x, y, z);
}
else if (op == 4)
cout << T.ask(1, nw[x], nw[x] + tr[x] - 1) % MOD << endl; //
else if (op == 3)
y = read(), T.add(1, nw[x], nw[x] + tr[x] - 1, y);
else
y = read(), cout << dfs_ask(x, y) << endl;
}
return 0;
}
```
by cymrain07 @ 2021-08-03 20:53:22
@[_TLEer_的小号](/user/362101)
by cymrain07 @ 2021-08-03 20:55:14
@[Grand_wizard](/user/236006) 谢谢谢谢/cy
by _TLEer_的小号 @ 2021-08-04 07:10:41