11.12 联测

A

可以转换为，对于每一条长度为 $k$ 的链，把链两端的点并为一个连通块。

答案是单调递增的，可以 $k$ 从 $n$ 到 $1$，每次遍历一遍树，把 $k$ 邻域并起来，$O(n^2\alpha(n))$。

观察到一件事：$siz$ 不小于 $2$ 的连通块只会有至多一个，设为 $S$。

考虑一个点何时被加入 $S$，发现当且仅当 $k\le d(u)$ 时 $u\in S$，$d(u)$ 表示离 $u$ 最远的点的距离，dp 求解即可。

B

枚举每个 $d$，发现挖掉的地方的只可能是 $d$ 的倍数，也就是说复杂度形如 $\sum_d\frac{n}{d}$。

对于剩下的部分，我们实际上要把每个段哈希下来，然后动态维护可重集组合数。

发现还要对可重集哈希，直接 $\text{Hash}(S)=\sum_{x \in S}x^3$，当然还可以随机赋权。

自然溢出被卡爆，使用 $10^{18}+7$ 作为字符串哈希模数。（痛失 50pts）