稍微的写一写我自己对树的同构的求法的理解…
(对于整篇文章,默认所有的树的边都是无向边,无编号)
如果哪里写错了、有歧义或者说的不明白,请随意打扰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}$…
总结一下步骤:
- 暴力枚举以哪个点为根
- 开始dfs,算出当前节点的哈希值
- 算出每个点为根节点时的哈希值
- 判断是否有某一对相等,如果有就是同构的
时间复杂度$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]独特的树叶 树哈希】