P9167 树形DP

spdarkle · 2024-12-26 17:13:28 · 题解

城市建造

如果逆着考虑，也等价于对于分开后的每个连通块，有且只有一个点能够连非本连通块的点（有边）且连接后连通。

也就是说这是“封闭”的，删去这个点之后这个连通块就彻底断了联系，并且这里显然这个点如果存在那么唯一。

可以证明，假设我们建立出原图的 dfs 树，可以发现每个“封闭”的连通块在 dfs 树上是连通的。

假设并不连通，那么至少存在两个点会与外界有边直接相连，矛盾。

接着，我们考虑 “封闭” 性在 dfs 树上的体现。

这等价于 dfs 树上，这个连通块只能由最浅层的点往外连边，且在这个最浅层的点的子树内，所有返祖边起点在非连通块内的，返祖边的终点只能够是这个最浅层的点。

下面称所有这样的“最浅层的点”为“特殊点”。

根据这个性质，我们不妨继续推导一下可以得到如下性质：

一条返祖边 y\to x，在原树链 y\to x 里，设 x 在这个方向的儿子是 t，那么 y\to t 的状态相同（也即如果 y 是特殊点，可以推出 y\to t 都是特殊点，同时 y 不是特殊点，则 y\to t 也都不是特殊点）
所有的 “特殊点” 在 dfs 树上是一个连通块（也就是说，删除所有的非特殊点后，所有特殊点只通过 dfs 树上的点仍然连通）。

考虑树形 DP，枚举分开后各个连通块大小 B，设 f_{u,0/1} 为子树 u，钦定 u 为特殊点，其所在连通块大小为 B 或 B+1 的方案数。

再考虑其转移，其实是将子树分为两部分，一部分接特殊点，一部分接普通子树（构成特殊点 u 负责的连通块）。一个朴素的想法是为了凑出这个大小，使用背包。

但其实这是不必要的，若 v\in Son(u)，且 v 的 f 值有一项是 1，那么说明 sz_v\ge B，而如果 f 的每一项都是零，那么必须参与 u 所负责连通块的构成，否则方案数就是零了。

不妨称 u 的儿子里 f 的每一项都是零的点为零点，其他为一点。

那么就会有如下合法情况：

在转移过程中，我们需要处理返祖边的所谓“状态相同”的限制，只需要求出 tarjan 算法中的 low 数组，并稍加讨论。

而如何算答案呢？我们枚举特殊点的连通块里最浅层的点，不妨设为 i，那么其合法，可以将 i 当作根，此时那外面的 n-i 个点都被钦定为非特殊点，此时我们再做一个类似于 dp 过程的答案计算即可。

这里有个问题就是可能会计算到全部使用 B+1 的情况，其实只需要再做一次计算，这次忽略掉所有与 f_{u,1} 相关的转移即可。

对于单个 B，复杂度 O(n)。

如果设特殊点个数是 a，那么 B=\lfloor\frac{n}{a}\rfloor，根据数论分块的知识，B 的个数是 O(\sqrt n) 级别的，因此总复杂度 O(n\sqrt n)。

常数优化：

当 sz<B 时不继续递归。

在做一些判断时，判断非法后即刻终止判断。

示例代码