1411

P1411 树 更好的阅读体验 简单 DP，但是毒瘤。开高精还卡空间。。 树形 DP。只关心根节点所处连通块大小，自然记 \(f_{i,j}\) 表示以 \(i\) 为根的子树中和 \(i\) 联通的 \(j\) 个点的贡献还没有被计算的答案。这里没有被计算的意思是实际的值为 \(j\times f ......

猜它是一个 multi-sg，只用算出每个位置的 sg 值。不过注意到这是一个图，你要求 mex 肯定不会太大，毛咕咕一下不会超过 $\sqrt{m}$。并且根据均摊，你求 mex 的复杂度是 $O(m)$ 的。接下来相当于你有一个数 $v$ 每次选一个点异或上它的 sg 值，求最后是 $0$ 的概 ......