P11993 [JOIST 2025] 迁移计划 题解

Description

JOI 王国由编号从 \(1\) 到 \(N\) 的 \(N\) 个城市组成。这些城市通过 \(N − 1\) 条单向道路连接。具体来说，对于每个 \(i = 2, 3, \ldots, N\)，存在一条从城市 \(i\) 通向城市 \(P_i\) 的道路。此处保证 \(1 \leq P_i < i\)。

每个城市有一个定义好的危险等级。首都（城市 \(1\)）的危险等级为 \(0\)。对于城市 \(i\)（\(2 \leq i \leq N\)），其危险等级定义为从该城市到城市 \(1\) 的路径中经过的道路数量。根据 JOI 王国的结构，从任意城市 \(i\) 到城市 \(1\) 的路径存在且唯一。

当前，城市 \(i\)（\(1 \leq i \leq N\)）居住着 \(K_i\) 只海狸。JOI 王国的总统 Bitaro 计划实施海狸迁移计划。该计划将在 \(Q\) 天内执行。在第 \(j\) 天（\(1 \leq j \leq Q\)），以下三类事件之一会发生：

• 迁移：当时刻所有居住在危险等级为 \(X_j\) 的城市的海狸会迁移到危险等级为 \(Y_j\) 的城市，该城市需满足从当前城市出发沿道路行进可达。保证 \(0 \leq Y_j < X_j\)。根据 JOI 王国的结构，每只海狸的迁移目的地唯一确定。
• 迁入：由于王国外的迁入，城市 \(A_j\) 的海狸数量增加 \(L_j\)。
• 调查： 调查当前时刻城市 \(B_j\) 居住的海狸数量。

作为 Bitaro 的下属，你发现无需实地考察即可根据迁移计划信息计算出每次调查事件时的海狸数量。

给定 JOI 王国的结构、各城市当前的海狸数量及迁移计划详情，请编写程序计算每次调查事件的结果。

\(2 \leq N,Q \leq 2\times 10^6\)。

Solution

首先这题是无法通过维护 bfs 序进行转移的，这么做完全无法优化。

考虑换个角度做，对一层的点一起维护。

注意到如果我们知道对于贡献到第 \(d\) 层的所有点的初始位置，那么这一层每个点的权值就能直接算了，权值就是初始位置在询问点子树里的贡献和。

这启发我们对于每一层维护一棵线段树，其中第 \(i\) 个位置的值是 dfs 序为 \(i\) 的点贡献到当前层的价值之和，合并时用线段树合并，查询时直接查询当前点子树对应的 dfs 序区间和即可。

时间复杂度：\(O((n+q)\log n)\)。

Code

#include <bits/stdc++.h>// #define int int64_tconst int kMaxN = 2e6 + 5;int n, q, sgt_cnt;
int a[kMaxN], rt[kMaxN];
int p[kMaxN], sz[kMaxN], dep[kMaxN], dfn[kMaxN];
std::vector<int> G[kMaxN];struct Node {int ls, rs, sum;
} t[kMaxN * 50];void pushup(int x) { t[x].sum = t[t[x].ls].sum + t[t[x].rs].sum; }int merge(int x, int y, int l, int r) {if (!x || !y) return x + y;if (l == r) {t[x].sum += t[y].sum;return x;}int mid = (l + r) >> 1;t[x].ls = merge(t[x].ls, t[y].ls, l, mid), t[x].rs = merge(t[x].rs, t[y].rs, mid + 1, r);pushup(x);return x;
}void update(int &x, int l, int r, int ql, int v) {if (!x) x = ++sgt_cnt;t[x].sum += v;if (l == r) return;int mid = (l + r) >> 1;if (ql <= mid) update(t[x].ls, l, mid, ql, v);else update(t[x].rs, mid + 1, r, ql, v);
}int query(int x, int l, int r, int ql, int qr) {if (!x || l > qr || r < ql) return 0;else if (l >= ql && r <= qr) return t[x].sum;int mid = (l + r) >> 1;return query(t[x].ls, l, mid, ql, qr) + query(t[x].rs, mid + 1, r, ql, qr);
}void dfs(int u, int fa) {static int dfn_cnt = 0;sz[u] = 1, dep[u] = dep[fa] + 1, dfn[u] = ++dfn_cnt;for (auto v : G[u]) {if (v == fa) continue;dfs(v, u);sz[u] += sz[v];}
}void dickdreamer() {std::cin >> n;for (int i = 2; i <= n; ++i) {std::cin >> p[i];G[p[i]].emplace_back(i), G[i].emplace_back(p[i]);}dep[0] = -1, dfs(1, 0);for (int i = 1; i <= n; ++i) {std::cin >> a[i];update(rt[dep[i]], 1, n, dfn[i], a[i]);}std::cin >> q;for (int i = 1; i <= q; ++i) {int op, x, y;std::cin >> op >> x;if (op == 1) {std::cin >> y;rt[y] = merge(rt[y], rt[x], 1, n), rt[x] = 0;} else if (op == 2) {std::cin >> y;update(rt[dep[x]], 1, n, dfn[x], y);} else {std::cout << query(rt[dep[x]], 1, n, dfn[x], dfn[x] + sz[x] - 1) << '\n';}}
}int32_t main() {
#ifdef ORZXKRfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifstd::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);int T = 1;// std::cin >> T;while (T--) dickdreamer();// std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";return 0;
}