P8990 [北大集训 2021] 小明的树
Alex_Wei
·
·
题解
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)。代码。