问题概要
给你一棵有 \(n\) 个点的树。树上有 \(m\) 个炸弹，第 \(i\) 个炸弹位于节点 \(p_i\)，爆炸范围是 \(w_i\)，会炸到任何一个距离 \(p_i\) 不超过 \(w_i\) 的点。一个节点上可能有多个炸弹。
求每个节点会被多少个炸弹炸到。
- \(1 \le n, m \le 5 \times 10^5\)
- \(1 \le w_i \le 50\)
解法
考虑有根树。
如果炸弹只能向下炸，也就是说一个点上的炸弹只能炸到这个点的后代，这问题就好做了。因此，我们把一个炸弹拆成多个只能向下炸的炸弹。比如点 \(u\) 处有一个威力是 \(3\) 的炸弹，我们把这个炸弹拆成四个只能向下炸的炸弹：对于每个 \(k = 0, 1, 2, 3\)，点 \(u\) 的第 \(k\) 级祖先处有一个只能向下炸的，威力是 \((3 - k)\) 的炸弹。
当我们把每个炸弹都这样拆解过后，每个点上可能有多个向下炸的炸弹，威力不尽相同。于是我们可以对每个点 \(u\) 算出一个数组 \((\mathrm{cnt}[u][i])_{i=0}^{50}\)，\(\mathrm{cnt}[u][i]\) 表示点 \(u\) 处有多少个向下炸的，威力是 \(i\) 的炸弹。
下面来谈如何计算 \(\mathrm{cnt}\) 数组。比如说点 \(u\) 处有一个威力是 \(3\) 的炸弹，\(u\) 的一到三级祖先依次是 \(p, q, r\)。那么上面说的，把这个炸弹拆成四个只能向下炸的炸弹，作用在 \(\mathrm{cnt}\) 数组上就是
cnt[u][3] += 1;
cnt[p][2] += 1;
cnt[q][1] += 1;
cnt[r][0] += 1;我们不妨将上述操作称为把炸弹上传，类似的，我们还可以把炸弹下传。比如说点 \(u\) 处有 10 个威力是 \(3\) 的，只能向下炸的炸弹，那么它们下传到 \(u\) 的孩子 \(v\) 处就相当于 10 个威力是 \(2\) 的，只能向下炸的炸弹。
cnt[v][2] += cnt[u][3]; 另一方面，我们注意到，在 \(u\) 的父节点 \(p\) 处的那一个威力是 \(2\) 的，只能向下炸的炸弹，它是不能往 \(u\) 下传的，不然就重复计算了。为了绕过这个限制，我们让点 \(u\) 处威力是 \(1\) 的炸弹减少一个，这样就把从点 \(p\) 传下来的那个威力是 \(1\) 的炸弹抵消了。合起来，把点 \(u\) 处的一个威力是 \(3\) 的炸弹拆成四个只能向下炸的炸弹，作用在 \(\mathrm{cnt}\) 数组上就是
cnt[u][3] += 1; cnt[u][1] -= 1;
cnt[p][2] += 1; cnt[p][0] -= 1;
cnt[q][1] += 1;
cnt[r][0] += 1;代码
const int maxn = 5e5 + 5;
vector<int> g[maxn];
int pv[maxn];
void dfs(int u, int p) {
pv[u] = p;
for (int v : g[u])
if (v != p)
dfs(v, u);
}
int cnt[maxn][51];
int ans[maxn];
void dfs2(int u, int p) {
ans[u] = accumulate(cnt[u], cnt[u] + 51, 0);
for (int v : g[u])
if (v != p) {
for (int i = 1; i <= 50; i++)
cnt[v][i - 1] += cnt[u][i];
dfs2(v, u);
}
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
// 找出每个点的父节点
dfs(1, 0);
// 上传炸弹
for (int i = 0; i < m; i++) {
int u, w;
cin >> u >> w;
for (int j = w; j >= 0; j--) {
cnt[u][j]++;
if (pv[u]) {
if (j >= 2)
cnt[u][j - 2]--;
u = pv[u];
} else break;
}
}
// 下传炸弹
dfs2(1, 0);
for (int i = 1; i <= n; i++)
cout << ans[i] << ' ';
cout << '\n';
}