Cayley 定理
结论 节点个数为\(n\)的无根标号树的个数为\(n^{n-2}\)。
这个结论在很多计数类题目中出现，要证明它首先需要了解 Prufer 序列的相关内容。接下来给出证明。
结论 节点个数为\(n\)的无根标号树的个数为\(n^{n-2}\)。
这个结论在很多计数类题目中出现，要证明它首先需要了解 Prufer 序列的相关内容。接下来给出证明。
其实这道题是一道大水题。我们知道成立条件为\(x_l \text{ xor } x_{l+1} \dots x_{mid} = x_{mid+1} \text{ xor } x_{mid+2} \dots x_{r}\)，然而这个运算可以直接移项：因为\(xor\)是自己本身的逆运算。然后为了保证\(r-l+1\)为偶数，我们只需要在 Trie 树末端维护奇偶计数即可。