@[Saiodgm](/user/482058) `build`函数里的`t.val`值不是`dfn[l]`
by cqbztz2 @ 2022-05-03 09:35:06
@[Little_ROY](/user/493271) 那是什么啊 /kk
我 DFS 的时候给 `dfn` 赋值就是赋的节点权值 qwq
by Liynw @ 2022-05-03 09:38:31
@[Saiodgm](/user/482058) 我眼瞎
by cqbztz2 @ 2022-05-03 09:40:06
```cpp
#include <cstdio>
#include <vector>
#define int long long
#define rep(i, j, k) for(int i = j; i <= k; ++i)
const int maxn = (int)1e6 + 5;
int n, q, r, mod, tot, w[maxn], ft[maxn], son[maxn], sum[maxn], dep[maxn], top[maxn], st[maxn], ed[maxn], dfn[maxn << 1];
std::vector<int> G[maxn];
namespace Segment_Tree {
struct _ {
int val, target, len;
} t[maxn << 2];
inline void swap(int &x, int &y) { x ^= y, y ^= x, x ^= y; }
void build(int p, int l, int r) {
t[p].len = r - l + 1;
if(l == r) {
t[p].val = dfn[l];
return;
}
int lc = p << 1, rc = p << 1 | 1, mid = (l + r) >> 1;
build(lc, l, mid);
build(rc, mid + 1, r);
t[p].val = (t[lc].val + t[rc].val);
return;
}
inline void pushdown(int p) {
if(t[p].target){
int l = p << 1, r = p << 1 | 1;
t[l].val = (t[l].val + t[l].len * t[p].target);
t[r].val = (t[r].val + t[r].len * t[p].target);
t[l].target = (t[l].target + t[p].target);
t[r].target = (t[r].target + t[p].target);
t[p].target = 0;
}
return;
}
void update(int p, int l, int r, int L, int R, int k) {
if(L <= l && r <= R) {
t[p].val = (t[p].val + t[p].len * k);
t[p].target = (t[p].target + k);
return;
}
pushdown(p);
int lc = p << 1, rc = p << 1 | 1, mid = (l + r) >> 1;
if(L <= mid)
update(lc, l, mid, L, R, k);
if(R > mid)
update(rc, mid + 1, r, L, R, k);
t[p].val = (t[lc].val + t[rc].val);
return;
}
int query(int p, int l, int r, int L, int R) {
if(L <= l && r <= R)
return t[p].val;
pushdown(p);
int lc = p << 1, rc = p << 1 | 1, mid = (l + r) >> 1, sum = 0;
if(L <= mid)
sum = (sum + query(lc, l, mid, L, R));
if(R > mid)
sum = (sum + query(rc, mid + 1, r, L, R));
return sum;
}
}
using namespace Segment_Tree;
void dfs1(int u, int fa) {
ft[u]=fa;
int len = G[u].size() - 1, mx = 0;
rep(i, 0, len) {
int v = G[u][i];
if(v != fa) {
dep[v] = dep[u] + 1;
dfs1(v, u);
sum[u] += sum[v];
if(sum[v] > mx) {
mx = sum[v];
son[u] = v;
}
}
}
++sum[u];
return;
}
void dfs2(int u, int fa, int tp) {
top[u] = tp;
dfn[++tot] = w[u];
st[u] = tot;
int len = G[u].size() - 1;
if(son[u]){
dfs2(son[u], u, tp);
}
rep(i, 0, len) {
int v = G[u][i];
if(v != fa && v != son[u])
dfs2(v, u, v);
}
// dfn[++tot] = w[u];
// ed[u] = tot;
return;
}
inline void Update(int u, int v, int x) {
while(top[u] != top[v]) {
if(dep[top[u]] < dep[top[v]])
swap(u, v);
update(1, 1, tot, st[top[u]], st[u], x);
u = ft[top[u]];
}
if(dep[u] > dep[v])
swap(u, v);
update(1, 1, tot, st[u], st[v], x);
return;
}
inline int Query(int u, int v) {
int s = 0;
while(top[u] != top[v]) {
if(dep[top[u]] < dep[top[v]])
swap(u, v);
s = (s + query(1, 1, tot, st[top[u]], st[u]));
u = ft[top[u]];
}
if(dep[u] > dep[v])
swap(u, v);
return s + query(1, 1, tot, st[u], st[v]);
}
signed main() {
scanf("%lld %lld %lld %lld", &n, &q, &r, &mod);
rep(i, 1, n)
scanf("%lld", &w[i]);
int u, v;
rep(i, 2, n) {
scanf("%lld %lld", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs1(r, 0);
dfs2(r, 0, r);
build(1, 1, tot);
int op, x, y, z;
rep(i, 1, q) {
scanf("%lld", &op);
if(op == 1) {
scanf("%lld %lld %lld", &x, &y, &z);
Update(x, y, z);
} else if(op == 2) {
scanf("%lld %lld", &x, &y);
printf("%lld\n", Query(x, y)%mod);
} else if(op == 3) {
scanf("%lld %lld", &x, &y);
update(1, 1, tot, st[x], st[x]+sum[x]-1, y);
} else {
scanf("%lld", &x);
printf("%lld\n", (query(1, 1, tot, st[x], st[x]+sum[x]-1))%mod);
}
}
return 0;
}
```
已经AC了
by cqbztz2 @ 2022-05-03 09:49:11
@[Saiodgm](/user/482058)
by cqbztz2 @ 2022-05-03 09:49:28
@[Saiodgm](/user/482058)
`Update`函数写错了
`update`只需要进行一次
操作4输出不需要`>>1`
by cqbztz2 @ 2022-05-03 09:51:10
@[Saiodgm](/user/482058)
还有亿点点小问题我忘记改了哪些了
by cqbztz2 @ 2022-05-03 09:52:54
@[Little_ROY](/user/493271) 谢谢大佬
原来是我的 `update` 和 `query` 传参写错了 qwq
by Liynw @ 2022-05-03 09:54:27