[BZOJ4754/Luogu4323][JSOI2016]独特的树叶(树Hash)

发布于 2018-05-24  200 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4754/Luogu4323][JSOI2016]独特的树叶(树Hash)

Description

JYY有两棵树A和B:树A有N个点,编号为1到N;树B有N+1个点,编号为1到N+1。JYY知道树B恰好是由树A加上一个叶节点,然后将节点的编号打乱后得到的。他想知道,这个多余的叶子到底是树B中的哪一个叶节点呢?

Tag

树Hash

解决思路

此题关键在于如何快速判断两个树是否同构。这里采用树$Hash$的方式。
先把第一棵树$Hash$出来,求出以任意一个点为根时的$hash$值。可以先选取一个点出发,求出以这个点为根时每一个点子树内的$hash$值,然后再从上向下传递一边,求出以每一个点为根的$hash$值。用$Map$记录下第一棵树中出现过的$Hash$值。
然后用同样的$Hash$方式,求出第二棵树上的$Hash$值,由于选择的点一定是叶子节点,所以求出分别去掉每一个叶子节点后的$Hash$值,在$Map$中进行查找。
由于有子树的关系,又因为要快速向下传递,这里采用异或和加权的方式求$Hash$,具体参见代码。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4754/Luogu4323][JSOI2016]独特的树叶(树Hash)


HNCJ OIer