AGC008 部分简要题解

F

不妨前考虑 \(70 \%\) 的部分分，\(s\) 全部为 \(1\)。

首先可以发现这个问题之所以困难是因为同一个联通子树可能可以被多个中心节点导出。

因此，我们考虑对于一个合法的联通子树，在一个特殊的节点上将其统计，这样可以不重不漏的计算。

为了方便我们令 \(f(x, d)\) 为以 \(x\) 为染色中心距离其不超过 \(d\) 的点构成点集。

考虑什么时候两个点会重复统计，不难得到如下观察：

若 \(f(x, d) \ne \{1, 2, \cdots n\}\) 则对于任意不同的 \(d\) 其 \(f\) 所对点集不同。

证明很显然。

因此，以下我们仅考虑不为全集的联通子树，显然全集是一定合法的。

若 \(f(x, d_1) = f(y, d_2)\) 那么一定有靠 \(x\) 一边的子树全部被染黑或靠 \(y\) 一边的子树全部被染黑。

若两边不存在一个子树全部被染黑，令 \(k = dist(x, y) > 0\) 则有：\(d_1 = d_2 + k, d_2 = d_1 + k\)，矛盾。

若 \(f(x, d_1) = f(y, d_2)\) 那么 \(x, y\) 构成的链上一定存在且恰好存在一个点使得其挂在链上的子树内存在点没有被染黑。

反证法，我们可以找到最靠近 \(x\) 子树内没有被全部染黑的点 \(u\) 和最靠近 \(y\) 子树内没有被全部染黑的点 \(v\)。

令 \(k_1 = dist(x, u), k_2 = dist(y, v)\)，则 \(u\) 子树内一定恰好是深度不超过 \(d_1 - k_1\) 的节点被染黑，\(v\) 子树内类似为 \(d_2 - k_2\) 的节点被染黑。

同时据此我们也可推出 \(u\) 子树内一定是被不超过 \(d_2 - k_2 - dist(u, v)\) 的节点被染黑，因为 \(u\) 子树内没有被全部染黑，所以深度不超过 \(d_1 - k_1\) 的点构成集合和深度不超过 \(d_2 - k_2 - dist(u, v)(dist(u, v) > 0)\) 构成集合一定不同，矛盾。

唯一性：若不存在则所有点被染黑，与一开始的假设不符。

推论：若 \(x, y\) 在树上相邻，那么一定恰好存在一个点子树内全部被染黑，一个没有全部被染黑。
若 \(f(x, d_1) = f(y, d_2)\)，则 \(x, y\) 路径上的每个点 \(u\) 都唯一存在一个 \(d'\) 使得 \(f(x, d_1) = f(u, d') = f(y, d_2)\)

若存在，唯一性由观察一可以保证。

对于存在性，根据观察二，我们不妨令 \(x\) 这边的子树全部被染黑，根据 \(y\) 这边的子树是否被染黑进行讨论。

若 \(y\) 这边的子树没有被全部染黑，则 \(x, y\) 路径上所有点（除了 \(y\)）子树内全被染黑，则考虑链上距离 \(x\) 最近的点 \(u\)。

令 \(k = dist(x, y)\)，有 \(f(u, d_2 + k - 1)\) 一定覆盖 \(f(y, d_2)\) 中除了 \(x\) 所在的子树内的点。

于此同时，\(f(u, d_2 + k - 1)\) 一定覆盖了 \(x\) 子树内距离其不超过 \(d_2 + k - 2\) 的点。

我们知道 \(f(y, d_2)\) 中仅包含距离 \(x \ \ d_2 - k\) 的点，当 \(k \ge 1\) 时恒有 \(k - 2 \ge -k\)。

若 \(y\) 这边的子树全部被染黑，令 \(u\) 为 \(x, y\) 路径上存在的唯一一个没有被全部染黑的节点。

则有 \(d_1 - dist(x, u) = d_2 - dist(y, u)\)，考虑证 \(f(x, d_1) = f(u, d_1 - dist(x, u)) = f(y, d_2)\)。

同时有 \(\forall v \in u \to y, maxdep(v) \le d_1 - dist(x, v) = d_1 - dist(x, u) - dist(u, v)\)，因此 \(f(u, d_1 - dist(x, u))\) 能覆盖 \(\forall v \in u \to y\)。

同理可证另一边，此时有 \((x, u), (u, y)\) 为第一种情况，即可证明所有情况。

推论 \(1\)：\(\forall S\) 满足 \(S\) 合法，那么合法的染色中心一定构成一颗联通子树。
推论 \(2\)：\(\forall S\) 满足 \(S\) 合法，\(S\) 合法的染色中心形成的联通子树 \(T\) 一定满足 \((u, v) \in T\) 且 \(f(u, d) = S\)，\(u\) 一侧子树内没有被全部染黑，\(v\) 一侧子树被全部染黑，则一定有 \(f(u, d) = f(v, d + 1)\)（根据观察四的证明易证）。
推论 \(3\)：\(\forall S\) 满足 \(S\) 合法，\(S\) 合法的染色中心形成的联通子树 \(T\) 一定满足存在且唯一存在 \(u \in T\) 使得 \(f(u, d) = S\) 且以 \(u\) 为根，\(\forall v \in T, f(u, d) = f(v, d + dist(u, d))\)（根据推论 \(2\) 易证）

因此，我们考虑在 \(S\) 的染色中心形成的联通子树 \(T\) 中 \(u \in T\) 且 \(f(u, d) = S\) 最小的 \(d\) 上统计 \(S\)。

因此，\(u\) 向外扩展半径为 \(d\) 的联通子树能统计当且仅当：

\(d < f_u\) 其中 \(f_u\) 为距离 \(u\) 最远点的距离。
根据推论 \(2\)，\(u\) 不存在一个子树使得删除这个子树后其他点全被染黑，即 \(d - 2 < g_u\)（\(g_u\) 为 \(u\) 往外和 \(f_u\) 所在点不在同一个子树的最远点 \(v\) 的距离）。

因此我们考虑换根求出 \(f, g\)，即可 \(\mathcal{O}(n)\) 计算答案。

考虑回到 \(s\) 中存在 \(0\) 的情况，我们还是考虑将所有合法的联通子树 \(S\) 在将所有点均看作合法情况下应该统计的点统计。

容易发现现在合法的 \(S\) 是部分分的子集，因此只需要将每个点的贡献考虑进关键点的影响即可。

因此 \(\forall u, d \in [0, \min(g_u + 1, f_u - 1)]\) 的每个 \(d\)，合法当且仅当 \(f(u, d)\) 的染色中心联通子树内至少存在一个合法点。

若 \(u\) 为关键点，显然所有的 \(d\) 均合法。

否则，考虑将整棵树以 \(u\) 为根，根据推论二当且仅当存在一个子树内的点全部被染黑且存在关键点。

于是我们令 \(h_u = \min\limits_{u \to v,\exists x \in S_v, s_x = 1} q_v\)（其中 \(q_v\) 为以 \(u\) 为根时 \(v\) 子树内的最远点距离），于是相当于对 \(u\) 的贡献限制了下界：\([h_u, \min(g_u + 1, f_u - 1)]\)，同样换根 \(\rm dp\) 出 \(h, q\) 后直接计算即可。

复杂度 \(\mathcal{O}(n)\)。

另外提一嘴，这个题存在另外一个思考方向。

我们不考虑选取关键点来统计，考虑将重复计算的联通子树减掉。

根据合法的染色中心构成联通子树这一性质，我们考虑使用 \(\forall\) 联通子树 \(V\) 满足 \(|V| - |E| = 1\) 来容斥。

具体地，我们考虑将所有点不包含全集的贡献先全部加上。

然后枚举每条边 \((u, v)\)，考虑计算出 \(u, v\) 构成相同的联通子树剪掉，这里其实就与上面做法的上下界等价。

因此这题存在一个不同的思考方式但导出的结果一模一样。

巴特西

AGC008 部分简要题解

F

最新文章

热门文章