稍微的写一写我自己对树的同构的求法的理解…
（对于整篇文章，默认所有的树的边都是无向边，无编号）
如果哪里写错了、有歧义或者说的不明白，请随意打扰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]独特的树叶 树哈希】
