树的同构——树哈希

稍微的写一写我自己对树的同构的求法的理解…

(对于整篇文章,默认所有的树的边都是无向边,无编号)

如果哪里写错了、有歧义或者说的不明白,请随意打扰qwq


什么样的两颗树算是同构的?

我们可以随意改变它们的形状(比如换根、交换儿子顺序),但是不能删边/加边,如果在某一种情况下,这两棵树长得一样,那么我们便称这两颗树是同构的。

以这两颗树为例,当我们把红色点当作根时,就会发现这两棵树其实长得一样,所以它们是同构的

如何判断?

方法1:

最开始当然是从暴力入手了,首先我们对于两棵树都枚举以哪个点为根节点,然后想办法判断确定根节点后是否同构。最最暴力的想法是对于当前节点,我们把它的儿子们按照子树大小进行排序,然后从小到大一一对应,但是仔细想一想之后我们就可以叉掉这个想法,因为当某两个子树大小相同时,我们并不清楚应该是哪两个对应。

这个时候我们就需要用哈希来帮助我们解决问题,设$hash[i]$表示以点$i$为根的子树的哈希值,$ size[i] $表示以点$i$为根的子树的大小,转移公式为:

$hash[i]=\sum \left ( hash[j]*base[j] \right )+size[i]$    $j$是$i$的儿子。

每次计算时需要把儿子的哈希值进行排序。

然后我们进行一遍dfs就可以算出我们枚举的根的哈希值。所以我们只需要对于两棵树分别求出以每一个点为根的哈希值,如果存在某一对相等,就是同构的。其实如果两棵树同构,那么排序后一定完全相同,所以不用排序,我们只需要判断第一棵树的所有点是否和第二颗树的第一个点(随便选的)相等即可,这样会少加一个$n\log{n}$…

总结一下步骤:

  1. 暴力枚举以哪个点为根
  2. 开始dfs,算出当前节点的哈希值
  3. 算出每个点为根节点时的哈希值
  4. 判断是否有某一对相等,如果有就是同构的

时间复杂度$O(n^{2} \log{n})$

例题:【BJOI2015 树的同构


方法2:

$O(n^{2}\log{n})$的复杂度我们一定是不能接受的,所以我们得尝试优化。

如果我们能不用去一一枚举所有的点,那么复杂度就降下来了。

对于一棵树,无论什么形状,它的重心都是不会变的,所以我们只需要把重心当作根,跑一遍dfs就可以了,如果重心在边上,那么就在这条边上新建一个点。

这样的话我们就可以把那个$O(n^{2}\log{n})$变成$O(n\log{n})$的了

例题:【独钓寒江雪


方法3:

我们先来看一道例题:【JSOI2016 独特的树叶

对于这个题的话,我们需要尝试去掉叶子节点并且快速判断出是否同构,也就是说我们需要知道以这些点为根的哈希值,所以在这里方法2就不好用了,我们更加不可能去用方法1,所以我们需要找出一个方法来快速算出以每个点为根的哈希值。

树形dp可以很好的胜任这个任务。我们先随便选择一个点进行一遍dfs,算出以这个点为根的哈希值,然后再从这个点开始进行另一个dfs,也就是开始dp。

我们在进行第一遍dfs的时候,已经把每个点的子树的哈希值计算并排序了,所以我们现在只需要计算:如果以当前点为根,它的父亲所代表的那颗子树的影响。

我们在dfs时同时传3个值,[当前点]、[父亲]、[父亲所代表的子树的哈希值]。

我们暂时先不考虑如何算出[父亲所代表的子树的哈希值],拿来直接用,所以我们马上就可以算出以当前点为根的哈希值。然后我们考虑如何算出[父亲所代表的子树的哈希值],也就是我们的[当前点]如果作为它的[儿子]的子树时的影响。

我们可以很简单的看出,我们要求的这颗子树其实就是以[当前点]为根但是刨除了我们要访问的[儿子]的这颗子树(也就是不包含红色三角的剩下的所有点)。
我们把所有的[当前点]的儿子的哈希值排序之后,求一个后缀和,进行循环的时候再维护一个前缀和,这样我们就可以快速的算出刨除某个[儿子]时[当前点]的哈希值,也就是[父亲所代表的子树的哈希值]。

至此,我们就求出了以每个点为根的哈希值,时间复杂度$O(n\log{n})$。

关于这个题的题解,可以看我的博客【[Jsoi2016]独特的树叶 树哈希

发表评论

电子邮件地址不会被公开。 必填项已用*标注