树哈希

引入

如何 DFS 到某一节点后，利用无序的子树 Hash 值，使得同构的树 Hash 值相同，不同构的 Hash 值尽量不同，且可以 \(O(1)\) 地计算删除部分子树后的 Hash 值？
树结构哈希，简称树哈希，就是解决这类问题的方法。
定义

以某个结点为根的子树的 Hash 值，就是以它的所有儿子为根的子树的 Hash 值构成的多重集的 Hash 值，即

\[H(u)=f(\{H(v)|v \in son(u)\})\]
其中 \(H(u)\) 表示以 \(u\) 为根的子树的 Hash 值，\(f\) 是多重集的 Hash 函数。
以树结构中使用的 Hash 函数为例：

\[H(u)=(c+\sum_{v \in son(u)}f(H(v))) \mod m\]
其中 \(c\) 为常数，一般使用 \(1\) 即可；\(m\) 为模数，一般使用 \(2^{64}\) 自然溢出或大素数；\(f\) 为整数到整数的映射，代码中优先考虑 xorshift。
xorshift

xorshift 是一个伪随机数生成算法，有 \(2^{32}-1,2^{64}-1\) 等周期。代码模版如下：
[code]ull xorshift(ull x) {    x ^= x > 7;    x ^= x > a >> b;        add(a, b);        add(b, a);    }    dfs(1, 0);    sort(hs + 1, hs + n + 1);    cout > n;    for (int i = 1; i > val;    for (int i = 1; i > lc >> rc;        lc = max(lc, 0);        rc = max(rc, 0);    }    h[0][0] = h[1][0] = h[2][0] = h[3][0] = 1001;    dfs(1);    cout > n;    for (int i = 1; i > val;    for (int i = 1; i > lc >> rc;    for (int i = 1; i  v;            if (v == 0) continue;            add(u, v);            add(v, u);        }        dfs(1, 0);        reroot(1, 0);        for (int i = 1; i  fmx[k]) {                smx[k] = fmx[k];                fmx[k] = h;            } else if (h > smx[k])                smx[k] = h;        }        for (int i = 1; i