2024/06/21(#54)：用满身尘土 换渺小幸福

重来几次才能清楚，
每段岔路与每个事故，
每条没有尽头旅途……

https://www.luogu.com.cn/training/531947。

能不能卷一点啊……

101 CF633F The Chocolate Spree

直接做。

102 POI2004 JAS | AGC009D

利用重心来做点分树看起来很不能做。

我们用 $d_i$ 给树染色，其代表在点分树上的深度。其合法条件是，对于相同的 $d_i$，其路径上一定存在一个比它大的点。

由于答案是 $O(\log n)$ 级别，因此我们可以考虑一些暴力做法。设 $f_i$ 代表子树内未被匹配的 $d$ 值集合。这样可以来求出当前位置能填什么。代码。

103 彼岸蔷薇

Portal.

做不出来还是有问题的啊……这种不断解剖问题，一步一步分析性质的能力还是要多练。

首先只需要看 $(u,u)$ 是否合法，然后每个 $u$ 可以贪心地 $O(n+m)$ 检查。

先求出一组合法解 $Q$，再进行调整。记 $Q$ 中 LCA 为关键点，根据性质，$u\in Q,(u,u)$ 不合法。

设 $T(d)$ 表示关键点 $d$ 控制的子树，即在贪心过程中它新覆盖的节点，即 $d$ 的子树去掉其子树内所有关键节点的子树得到的连通块。$cov(x)$ 表示是谁覆盖（控制）了 $x$。

考虑一条路径 $u\rightarrow v$ 对合法点的贡献：

• LCA 是关键点。如果使用这条路径覆盖，那么在 $u,v\in T(d)$ 时，$T(d)\backslash\{u\rightarrow v\}$ 均可以被覆盖。
• 不是关键点。此时 $(u,v)$ 必定跨过一个关键点 $d$，然后 $(u,v)$ 的 LCA $x$ 是 $d$ 的祖先。此时令 $u,x$ 不被同一个节点控制，那么 $v,x$ 必须要被同一个节点控制，否则 $x$ 不合法，而控制 $u$ 的点再往上找一个关键点就应该是控制 $x$ 的点。然后此时 $T(d)\backslash\{u\rightarrow d\}$ 合法。

这个东西很好实现，使用树上差分，将路径上的点和关键点 +1，只有当路径权值比关键点权值小的时候才合法。代码。

104 P2664 树上游戏

考虑换根 DP。维护数组 $a_x$ 表示当前根 $rt$ 确定之后，颜色 $x$ 对于 $rt\rightarrow i(i\in [1,n])$ 的贡献之和。

换根时只需要维护在 $x$ 的子树中，$c_{fa(x)}$ 的贡献即可。

105 CEOI2017 One-Way Streets

首先一个边双内部内部肯定无法确定，我们只需要判断割边。

边双缩点建立出树，一个限制 $u\rightarrow v$ 表示强制钦定这条链上的方向。由于一定有解，因此直接使用树上差分维护即可。

106 AGC008F Black Radius

看上去怎么都得数重？排除掉全黑的情况，钦定我们在状态相同的时候，只数那个 $d$ 最小的。不难发现，这时对应的染色点是唯一的。

也即是说，设 $f(u,d)$ 代表 $u$ 的大小为 $d$ 的邻域，那么 $f(u,d)$ 被计入答案，当且仅当不存在与 $u$ 相邻的点 $v$ 使得 $f(u,d)=f(v,d-1)$。要不出现这种情况，应该满足以 $u$ 为根的次小深度子树深度 $\ge d-1$。

由于有的点不可以取到，因此相当于它存在一个最小合法 $d$，满足存在 $d_0$ 使得 $S(v,d_0)=S(u,d)$。也就是说，$d$ 的下限为所有含有 $1$ 的子树的深度的最小值。