哈希

哈希最基本的功能就是判重判等、统计同构。

字符串哈希¶

其实就是求 siz[]（可以加个取模，或者自然溢出）：

\[ h[u]=1+\sum\limits shift(h[v]) \]

其中 shift() 采用xor shift。这个东西还可以换根。

容易得出，先手必胜当且仅当存在一个元素出现了奇数次。对于每个点到根的链求异或哈希，每个点都有：n减去哈希值和自己相等（即异或后不存在奇数次）

异或可以方便查询集合内元素是否都出现了偶数次。当然也可以扩展到 \(k\) 次。