BZOJ 4337 树的同构

By NodeKey in ACM on

昨天的多校有一道需要树Hash的基础，于是就找到了这题。这题应该算得上是树Hash的裸题了。 树Hash的方法其实十分简单。有兴趣的看一下我的这篇 博文 然而上面那片博文是定根结点的，如果根节点固定，对于树的形态进行Hash，实际上是非常简单的。 再次简单说一下树Hash的原理，对于有根树，我们Hash的是树的形态，而树的形态则有每一层的结点个数与结点所连接的相同父亲结点所决定。 因此我们对于同一层的并且是同一个父亲的结点作一个相同的Hash，那么就得到了我们要得答案。 不过也有一个简单也正确的写法，就是将同一层并且具有相同孩子结点数量作同一个Hash，也可得到我们想要的结果。 但上述方法是针对有根树而言，如果不定根，则不好判断。 这是我们可以对小数据选择枚举所有结点，对较大数据选择寻找树的重心(不会超过两个)。 下面放上题解。 2017-8-14更新： 该理论用于有根树已经被推翻，对于无根树，也就是这道题，莫名适用，也许是数据水…… 题意： 给你( n ) 棵树，每棵树用给定每个结点的父亲予以表示。问对于每一棵树，与它同构的并且序号最小的是哪一棵。…

树的同构 ( 附带 POJ 1635 )

By NodeKey in ACM on

前言 POJ 1635 这是刷字符串的时候被煞笔天海放进来的一道题，题意是让你判断两棵树是否同构。 我想他的主要目的应该是听了肥宅带鱼的B话，把树上的最小表示法也放进来了…… 这特么完全不是一个算法好么 虽然可以转化 必要知识 (可跳过 首先我们必须得知道两棵树的同构是如何定义的。 一棵树通过不断交换他的子树位置，最后能够与另一棵树完全相同，则称这两颗树同构。 ( 例子我就不举了…… 树上的最小表示法 最先看得就是树上的最小表示法，其实树上的最小表示法，并没有什么难的，反而可以说是以中非常暴力的方法。判断同构，非常慢，在这里我并不推荐。 简单说一下原理。 通过dfs找出当前节点的每个子树的序列表示，再对所有子树进行排序，再将排序后的序列相加来作为当前根树的序列表示。 以POJ 1635 为例的代码 570 ms #include #include #include #include #include using namespace std;…