我们用字符串哈希可以判断字符串相等，那么判断树同构呢？
两棵树同构，当且仅当存在将其中一棵树的节点打乱的方案，使得打乱后两棵树完全相同。
树哈希，就是把字符串哈希搬到树上来。对于两棵同构的有根树，其哈希值相同。下面介绍一种构造方式。
\[f_i=\sum\limits_{x\in son(i)}f_xp_{|S(x)|} \]其中 \(S(x)\) 表示 \(x\) 的子树中节点所构成集合，\(son(x)\) 表示 \(x\) 的儿子构成的集合，而 \(p_x\) 为一个权值。一般可以取第 \(x\) 个质数。这样哈希有什么好处呢？
标签：同构,打乱,笔记,son,学习,哈希,字符串,两棵树 From： https://www.cnblogs.com/tulipenoire/p/17726813.html