简化代码
注意 hash 的值具有可加减的特性,可以极大程度的简化代码。
同时可以维护可能作为答案的 “匹配池” 中的 hash 值,这样就不用进行(超级 dirty work 的)树加减了。
树哈希是一种集合哈希(?),所以支持加减!!!
hash 函数
我也不知道为什么大家都在用这个 hash 函数
ull shift(ull x) {return x ^= mask, x ^= x << 13, x ^= x >> 7, x ^= x << 17, x ^= mask, x;}
mask = mtrnd() * mtrnd();
当然,这个函数够随机就行(应该)。
特征值
- 无根树 hash 也可以采取“把以每个节点为根得到的 hsh 值都加起来(注意用另一个 hsh 函数)”(这个不知道好不好,但是好写,可能不够强)
- 重心
- 深度/节点大小