按照 $OI\;WIKI$ 的说法，其实就是给树的每一个节点定义了一个哈希值，随着子树结构不同，不同子树的根节点的哈希值不同

根节点与其子节点的哈希值之间的关系为:

$$f(root) = \displaystyle{(c + \sum g(son))\; mod\;m}$$

• 一般情况下 $c = 1$
• $m$可以是 $2^{64}$ 从而使得结果自然溢出

为了防止卡哈希，函数 $g$ 会写成:

(具体模板见OI WIKI)

const ULL mask = rand();
ULL shift(ULL x)
{
    x ^= mask;
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    x ^= mask;
    return x;
}

例题:

1.CF1800-Div3 G Symmetree

code

2.AcWing476 对称二叉树

code