震惊！乘起来乘常数加常数的树哈希其实是对的

zhuzhu2891 · 2025-12-17 14:32:59 · 算法·理论

我们有一个经典的有根树哈希算法：f(T)=x\prod(f(T_i)+y)，T_i 表示 T 的一个子树，这个算法一直以来被认为是不正确的，然而我们发现在随机 x,y 的情况下，这个算法判断两棵树是否同构的错误率只有 O(\frac n{\text{mod}})，也就意味着只要不对着卡就是对的。

我们发现对于一棵确定的有根树 T，f(T) 的值是一个关于 x,y 的二元多项式，只需证 f(S)=f(T) 时必有 S 同构于 T 即可。然后我们进行归纳，因此只需要证明 f(S)=f(T) 时必有 \{f(S_i)\}=\{f(T_i)\}。

如果 f(S_i)+y 在有理数域内是不可约的，那么上一条显然成立，因为我们有任意元整系数多项式的唯一分解定理。

假设 f(S_i)+y=A\times B，考察 [x^0]A 与 [x^0]B，显然 [x^0]A\times[x^0]B=y。然后我们考察 [y^0]A 与 [y^0]B，显然 [y^0]A\times[y^0]B=x^{|S_i|}（|S_i| 是 S_i 的大小），但是我们注意到 [x^0y^0]A=1，所以 [y^0]A=1,[y^0]B=x^{|S_i|}，注意到 f(S_i)+y 在 x 的次数大于等于 |S_i| 时只有一项 x^{|S_i|}，因此 A=1，f(S_i)+y 其实不可约。

于是我们证明了两棵有根树不同时，对应的二元多项式也不同（以上证明也可以直接被搬到 \mathbb F_p，所以对于 \bmod p 的情况这一点也成立），根据 schwartz zippel lemma，我们随机取 x,y，错误率就是 O(\frac n{\text{mod}}) 的。