能把代码贴全吗？
by forgotmyhandle @ 2024-03-30 12:06:18
@[Jefferyz](/user/1022282) 1到底那条链有深度很深的点，但是跳一次就寄。
by xiaozengX @ 2024-03-30 12:19:16
@[xiaozengX](/user/321529) 只有打注释的2行有问题，换成dfn比较就AC了，不理解为什么跳到同一条链上dfn序应该是连续和dep等价的，为什么不能用dep比较呢？
by Jefferyz @ 2024-03-30 12:26:27
@[forgotmyhandle](/user/573377)
```
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
char c;
bool flag = false;
while ((c = getchar()) < '0' || c > '9') if (c == '-') flag = true;
int res = c - '0';
while ((c = getchar()) >= '0' && c <= '9') res = (res << 3) + (res << 1) + c - '0';
return flag ? -res : res;
}
const int maxn = 6e5 + 10;
int tree[maxn << 2], tag[maxn << 2], a[maxn];
int n, s[maxn], son[maxn], dep[maxn], fa[maxn], top[maxn], dfn[maxn], df, M, R, P, tmp[maxn];
int ls(int p) { return p << 1; }
int rs(int p) { return p << 1 | 1; }
void pushup(int p) {
tree[p] = (tree[ls(p)] + tree[rs(p)]) % P;
}
void addtag(int p, int l, int r, int d) {
tree[p] = (tree[p] + (r - l + 1) * d) % P;
tag[p] = (tag[p] + d) % P;
}
void pushdown(int p, int l, int r) {
if (!tag[p]) return;
int mid = (l + r) >> 1;
addtag(ls(p), l, mid, tag[p]);
addtag(rs(p), mid + 1, r, tag[p]);
tag[p] = 0;
}
void build(int p, int l, int r) {
if (l == r) {
tree[p] = a[l];
return;
}
int mid = (l + r) >> 1;
build(ls(p), l, mid);
build(rs(p), mid + 1, r);
pushup(p);
}
int query(int p, int lp, int rp, int l, int r) {
int ans = 0;
if (lp >= l && rp <= r) return tree[p];
pushdown(p, lp, rp);
int mid = (lp + rp) >> 1;
if (l <= mid) ans = (ans + query(ls(p), lp, mid, l, r) % P) % P;
if (r > mid) ans = (ans + query(rs(p), mid + 1, rp, l, r) % P) % P;
return ans;
}
void update(int p, int lp, int rp, int l, int r, int d) {
if (lp >= l && rp <= r) {
addtag(p, lp, rp, d);
return;
}
pushdown(p, lp, rp);
int mid = (lp + rp) >> 1;
if (l <= mid) update(ls(p), lp, mid, l, r, d);
if (r > mid) update(rs(p), mid + 1, rp, l, r, d);
pushup(p);
}
struct Edge {
int to, w, next, from;
} edge[maxn << 1], e[maxn << 1];
int head[maxn << 1], cnt;
void init() {
for (int i = 0; i <= n; i++) head[i] = -1;
cnt = 0;
}
void add_edge(int u, int v, int w) {
edge[cnt].to = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt++;
}
void dfs(int x, int ff) {
fa[x] = ff;
dep[x] = dep[ff] + 1;
s[x] = 1;
for (int i = head[x]; ~i; i = edge[i].next) {
int y = edge[i].to;
if (y == ff) continue;
dfs(y, x);
s[x] += s[y];
if (s[y] > s[son[x]]) son[x] = y;
}
}
void dfs2(int x, int topf) {
top[x] = topf;
dfn[x] = ++df;
if (son[x]) dfs2(son[x], topf);
for (int i = head[x]; ~i; i = edge[i].next) {
int y = edge[i].to;
if (y == fa[x] || y == son[x]) continue;
dfs2(y, y);
}
}
int lca(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] > dep[top[y]]) x = fa[top[x]];
else y = fa[top[y]];
}
return dep[x] > dep[y] ? y : x;
}
void path_add(int u, int v, int z) {
int fu = top[u], fv = top[v];
while (fu != fv) {
if (dep[fu] >= dep[fv]) update(1, 1, n, dfn[top[u]], dfn[u], z), u = fa[top[u]];
else update(1, 1, n, dfn[top[v]], dfn[v], z), v = fa[top[v]];
fu = top[u];
fv = top[v];
}
if (dfn[u] >= dfn[v]) update(1, 1, n, dfn[v], dfn[u], z);
else update(1, 1, n, dfn[u], dfn[v], z);
}
int path_chk(int u, int v) {
int res = 0;
int fu = top[u], fv = top[v];
while (fu != fv) {
if (dep[fu] >= dep[fv]) res = (res + query(1, 1, n, dfn[top[u]], dfn[u]) % P) % P, u = fa[top[u]];
else res = (res + query(1, 1, n, dfn[top[v]], dfn[v]) % P) % P, v = fa[top[v]];
fu = top[u];
fv = top[v];
}
if (dfn[u] >= dfn[v]) res += query(1, 1, n, dfn[v], dfn[u]);
else res += query(1, 1, n, dfn[u], dfn[v]);
return res;
}
void tree_add(int u, int z) {
//printf("%lld %lld", dfn[u], dfn[u] + s[u] - 1);
update(1, 1, n, dfn[u], dfn[u] + s[u] - 1, z);
}
int tree_chk(int u) {
return query(1, 1, n, dfn[u], dfn[u] + s[u] - 1) % P;
}
signed main() {
n = read(), M = read(), R = read(), P = read();
init();
for (int i = 1; i <= n; ++i) tmp[i] = read();
for (int i = 1; i < n; ++i) {
int x = read(), y = read();
add_edge(x, y, 1);
add_edge(y, x, 1);
}
dfs(R, 0);
dfs2(R, R);
for (int i = 1; i <= n; ++i) a[dfn[i]] = tmp[i];
build(1, 1, n);
for (int i = 1; i <= M; ++i) {
int opt = read();
if (opt == 1) {
int x = read(), y = read(), z = read();
path_add(x, y, z);
}
if (opt == 2) {
int x = read(), y = read();
printf("%lld\n", path_chk(x, y) % P);
}
if (opt == 3) {
int x = read(), z = read();
tree_add(x, z);
}
if (opt == 4) {
int x = read();
printf("%lld\n", tree_chk(x) % P);
}
}
return 0;
}
```
by Jefferyz @ 2024-03-30 12:28:26
你给的这代码用 dep 比也能过啊
[纪录](https://www.luogu.com.cn/record/153459675)
by forgotmyhandle @ 2024-03-30 15:39:27