自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:44:23，当前版本为作者最后更新于2023-02-13 12:31:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

D3T1. P8990 [北大集训 2021] 小明的树

从白点限制入手不好描述一棵树是否美丽，因为白点的限制是子树限制，而操作使得子树关系难以维护。为此，我们希望从边的角度描述限制，且每条边的贡献独立，这样，支持题述操作就容易了。

换种角度，考虑黑点限制，发现一棵树是美丽的，当且仅当每个黑点没有白点祖先，进一步转化就是 黑点连通。

设 $c_i$ 表示时刻 $i$ 黑点连通块的数量。连通块数为 $|V| - |E|$，所以 $c_i$ 等于时刻 $i$ 的黑点数量 $n - i$，减去两端都是黑点的边数，初始为 $n - 1$。因此，初始化所有 $c_i$ 为 $1 - i$。对于每条边，设它第一次某端被点亮的时刻为 $t$，则 $c_t\sim c_{n - 1}$ 加 $1$。很显然，$t = \min(b_u, b_v)$，其中 $b_i$ 表示 $i$ 被点亮的时刻（$b_1 = n$）。

同样的，为方便统计答案，考虑从边的角度入手。想到这一点后，我们很容易发现一棵美丽的树的权值就是两端颜色不同的边的数量，设为 $v_i$，而一条边两端颜色不同的时刻就是 $\min(b_u, b_v)\sim \max(b_u, b_v) - 1$。

因此，答案相当于所有 $c_i = 1$ 的 $v_i$ 之和。操作产生的影响为 $\mathcal{O}(1)$ 次区间 $c, v$ 修改，又因为 $c_i\geq 1$，所以线段树维护区间最小值，最小值数量以及对应权值之和即可。

时间复杂度 $\mathcal{O}((n + q)\log n)$。代码。