菜王的 blog

这个数据范围显然考虑 meet in the middle。但是直接做可能不好做，我们考虑找到树的一个重心 $rt$，那么连通块根据是否包含 $u$ 被分为两类。对于第二类，直接枚举即可，根据重心的定义，这部分时间复杂度为 $O(2^{\frac n2})$。

考虑第一类连通块。我们考虑以 $rt$ 为根，那么我们需要将 $rt$ 的儿子的子树分为两部分，使得两部分的大小之和更大的那个尽量小，设这个大小为 $B$，由于两部分独立，这样我们就能直接以 $O((n - B)2^B)$ 的时间 meet in the middle 了。

考虑证明 $B < \frac 23n$。显然 $rt$ 的度数 $\le 3$ 的时候，结论成立。当 $rt$ 的度数 $> 3$ 的时候，$rt$ 的儿子的子树中，最小与次小的子树大小之和显然 $\le \frac n2$，我们将这两个子树合并为一个子树，就能归纳到度数减一的情况。

那么这个题就做完了。代码在这里。