如果一个点 uVu\in V’ 我们称 uu 是被选择的,在选取 VV’ 所有点后 EE’ 可以唯一确定,所以只需要统计有多少种 VV’ 的选取方式。考虑每个点双联通分量,其中恰好只有一个点被选择或者全部选择(否则一定存在路径 $x\leftrightarrow a\leftrightarrow b\leftrightarrow\cdots \leftrightarrow y$ 其中只有 x,yx,y 是被选择的,移除 EE’ 的边后 x,yx,y 仍然联通)。受此启发,可以建立圆方树处理。此外还需要满足圆方树上被选择的点构成一个联通快。每个被选择的圆点对应的剩余联通块大小等于 nn 减去其相邻的被选择的点对应的子树大小。

假设 V=k|V’|=k,我们会发现联通块大小只能是 n/k\lfloor n/ k\rfloor 或者 n/k\lceil n/k\rceil,最多只会有 O(n)O(\sqrt n) 个,所以我们可以枚举这些大小 ss,在树上 DP 求出合法的选择方案 VV’ 使得每个点对应的联通块大小为 ss 或者 s+1s+1。设 fuf_u 表示只考虑子树 uu 中的点,且 uu 是被选中的合法方案数。对于方点,只需求出每个孩子 fvf_v 的乘积。对于圆点,我们将孩子节点分为三类:子树大小 <s<s, =s=s 或者 s+1\ge s+1 的(称作 A,B,C 类点)。对于 A 类点,只能依附于点 uu 之上,设 sumsum 表示它们的大小之和;对于 C 类点,只能是独立存在的,只需求出它们 ff 的乘积,记做 prodprod;另外对于 BB 类点,可以选择独立存在,也可以是依附于 uu 上,我们将这类点的数量记做 cntcnt。如果 sum+1sum+1sss+1s+1,则 fuf_u 可以累加一。如果 sum+1sum+1 与子树之外的点大小之和为 sss+1s+1 我们可以把 prodprod 累加到答案上(强制所有选择方案的贡献在联通块的最上方统计)。之后考虑存在一个 B 类点依附 uu 的情况,此时令 sumsum += ssprod ×= cntprod~\operatorname{\times =} ~cnt,重复上述统计过程,不难发现所有情况都被考虑到了。

时间复杂度 O(nlogn)O(n\log n)。另存在 O(n)O(n) 做法。

0 comments

No comments so far...