树哈希 学习笔记

1.做法(from peehs_moorhsum)

设 \(h(u)\) 表示一个点的哈希值，\(f\) 为一随机函数。

\(h(u)=1+\sum\limits_{v\in son_{u}}f(h(v))\)

首先 \(f\) 的选择大概率是随机的，只要尽量不选多项式即可。（微调一下）。

ull d(ull x){
    return x*x*x*19260817+20220827;
}
ull f(ull x){
    ull cal=d(x & ((1<<31)-1)) + d(x>>31);
    return cal;
}

板子题：树哈希

2.例题

Luogu P5043

因为是无根树，所以我们要选一个根来方便比较。选择树的重心来做是比较好的，但是一棵树最多可以有两个重心。所以判断是都同构有很多条件。

两棵无根树是否同构首先要看重心数量是否相同，然后判断是否两棵树中至少有一对重心的哈希值是相同的。

代码：Link

HDU 6647

首先这道题非常恶心，我的代码必须开了 \(\rm Ofast\) 才能通过。

我们首先考虑如果根确定的话，怎么统计答案。

我们考虑遍历整颗树，对于每一个节点统计以当前节点为根的子树内部答案为多少，设其为 \(res_u\) 。当考虑到一个点的时候，我们在不考虑重复的情况下，其所有儿子的括号序的合并的总数为：\(\mid son_u\mid \times \prod_{v\in son_u} res_v\) 。然后我们把所有重复的删去，我们发现当两棵树同构是他们的先后位置不会改变序列的形态，所以我们要把所有的同构的子树全部找出来，设 \(cnt_{u,v}\) 表示 \(u\) 子树中哈希值为 \(v\) 的数量，那么最后的结果就是：\(res_u=\mid son_u\mid \times \prod_{v\in son_u} res_v \times \prod_{k}\frac{1}{cnt_{u,k}}\) 。

那么一遍 \(DFS\) 就可以求出来以特定点为根的所有答案。

对于所有点，其实只要再换个根就可以了，但是换根的难易程度依赖树哈希的写法，使用上面介绍的做法，可以比较轻松的实现换根，写起来比较容易。

代码：Link

Luogu P4323

无根树哈希板子题。

因为 \(B\) 中多出来的点一定为叶子节点，那么以这个点为根时，这个点有唯一的儿子，且删去这个点后，新树和 \(A\) 树同构。

所以我们可以 \(O(n)\) 的算出来以 \(A\) 中任何一个点为根的有根树哈希值和以 \(B\) 中任何一个点为根的有根树哈希值。

然后检查 \(B\) 中每一个度数为 \(1\) 的点，看他的儿子的哈希值是否在 \(A\) 树计算出来的哈希值中。这样找到最小值即可。

代码：Link