自动搬运

查看原文

来自洛谷，原作者为

	Xiao_Xiao_Yu 多优减判等转律正反贪贡序

搬运于2025-08-24 22:59:33，当前版本为作者最后更新于2024-07-11 20:24:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P10603 烁烁的游戏 题解

题意：给定一棵 $n$ 个点带权的树（边权均为 $1$），初始所有点权为 $0$。给出 $m$ 次操作：询问一个点的点权，或修改距离一个点不超过 $d$ 的所有点的点权。

前置知识

建议先完成以下知识点的题目再来挑战本题。

树状数组：见 P3374 及 P3368。

点分树：见 P6329。

分析

本题与 P6329 的任务要求和解法都较为相似，不过该题为单点修改、区间查询，而本题为区间修改，单点查询。这里的区间实际上指的是树上连通块。

涉及维护树上连通块信息的问题优先考虑使用点分树解决，按照点分树的常见套路，在每个点上建立数据结构维护信息，在修改/查询时遍历节点在点分树上的祖先并修改/查询这些点上的数据结构信息。通常实际上需要建立多个数据结构，用容斥原理防止部分答案被重复计算。

对于本题，因为我们不便直接修改整个连通块内所有节点的信息，所以我们使用「标记」的思想：进行修改操作时仅在输入的节点 $x$ 处打上一个标记，并使得在查询时能够根据所有的标记算出累计的影响。点分树上遍历祖先的操作恰好达到了这一目的。

思路

在每个点上建立两个树状数组 $c_{i_0},c_{i_1}$ 维护节点 $i$ 的点分子树中的节点受到修改的影响。这里我们利用树状数组维护差分数组的技巧，$c_{i_0}$ 的前缀和 $\sum_{j=0}^{k}c_{i_0,j}$ 维护的是节点 $i$ 的点分子树中与节点 $i$ 在原树上的距离不超过 $k$ 的节点受到的累计影响，$c_{i_1}$ 的前缀和 $\sum_{j=0}^{k}c_{i_1,j}$ 维护的是节点 $i$ 的点分子树中与节点 $i$ 的点分父节点在原树上的距离不超过 $k$ 的节点受到的累计影响。

进行修改操作时，首先对 $c_{x_0}$ 进行区间修改，在 $[0,k]$ 的值域上加上 $w$（由于是差分数组，实际只需进行 $2$ 次单点修改即可）。然后遍历 $x$ 的所有点分祖先，对祖先 $u$ 在 $c_{u_0}$ 的 $[0,k-\text{dis}(x,u)]$ 的值域上加上 $w$，其中 $\text{dis}(x,u)$ 表示 $x$ 与 $u$ 在原树上的距离。注意到此时重复计算了 $u$ 的 $x$ 方向上的子树内那一部分的答案，所以需要在 $c_{x_1}$ 的 $[0,k-\text{dis}(x,u)]$ 值域上减去 $w$。

查询操作则更简单，直接遍历 $x$ 的所有点分祖先 $u$，累加 $c_{u_0}$ 的前缀和 $\text{ask}(c_{u_0},\text{dis}(u, x))$ 和 $c_{u_1}$ 的前缀和 $\text{ask}(c_{u_1},\text{dis}(fa_u, x))$ 即可。其中 $fa_u$ 表示 $u$ 在点分树上的父亲。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;

int n, m, x, k, w, ans;
char s[3];
int sum, siz[maxn], weight[maxn], root, fa[maxn];
bool vis[maxn];
vector<int> g[maxn];
vector<int> c[maxn][2];
int d[maxn], f[maxn][20];

void dfs(int u) {
	for (int v : g[u]) {
		if (d[v]) continue;
		d[v] = d[u] + 1;
		f[v][0] = u;
		for (int i = 1; i <= 18; ++i) 
			f[v][i] = f[f[v][i - 1]][i - 1];
		dfs(v);
	}
}

int lca(int x, int y) {
	if (d[x] < d[y]) swap(x, y);
	for (int i = 18; i >= 0; --i)
		if (d[f[x][i]] >= d[y]) x = f[x][i];
	if (x == y) return x;
	for (int i = 18; i >= 0; --i)
		if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
	return f[x][0];
}

int dist(int x, int y) {
	return d[x] + d[y] - 2 * d[lca(x, y)];
}

void add(vector<int> &c, int y, int d) {
	for (; y < c.size(); y += (y & -y)) {
		c[y] += d;
	}
}

void add(vector<int> &c, int l, int r, int d) {
	add(c, l + 1, d);
	add(c, r + 2, -d);
}

int ask(vector<int> &c, int y) {
	++y;
	int res = 0;
	for (; y; y -= (y & -y)) 
		if (c.size() > y) res += c[y]; 
	return res;
}

void calcsize(int u, int fa) {
	siz[u] = 1;
	weight[u] = 0;
	for (int v : g[u]) {
		if (v == fa || vis[v]) continue;
		calcsize(v, u);
		siz[u] += siz[v];
		weight[u] = max(weight[u], siz[v]);
	}
	weight[u] = max(weight[u], sum - siz[u]);
	if (weight[root] > weight[u]) root = u;
}

void build(int u) {
	c[u][0].resize(siz[u] + 10);
	vis[u] = true;
	for (int v : g[u]) {
		if (vis[v]) continue;
		sum = siz[v];
		root = 0;
		calcsize(v, 0);
		calcsize(root ,0);
		fa[root] = u;
		c[root][1].resize(siz[root] + 10);
		build(root);
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1, u, v; i < n; ++i) {
		scanf("%d %d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	d[1] = 1;
	dfs(1);
	sum = n;
	weight[root = 0] = 0x3fffffff;
	calcsize(1, 0);
	calcsize(root, 0);
	build(root);
	while (m--) {
		scanf("%s %d", s, &x);
		if (s[0] == 'Q') {
			ans = ask(c[x][0], 0);
			for (int p = x; fa[p]; p = fa[p]) {
				ans += ask(c[fa[p]][0], dist(fa[p], x));
				ans += ask(c[p][1], dist(fa[p], x));
			}
			printf("%d\n", ans);
		} else {
			scanf("%d %d", &k, &w);
			add(c[x][0], 0, k, w);
			for (int p = x; fa[p]; p = fa[p]) {
				int d = dist(fa[p], x);
				if (k < d) continue; 
				add(c[fa[p]][0], 0, k - d, w);
				add(c[p][1], 0, k - d, -w);
			}
		}
	}
	return 0;
}