@ysner
2018-06-10T10:20:55.000000Z
字数 2032
阅读 2092
哈希
树
有一颗大小为的树,现加上一个节点并打乱编号,形成树,询问加上的节点最后编号是多少?
判断树的同构显然需要树哈希。
可以先将树中以每个节点为根的哈希值算出来存进一只中,
然后在树中随便找一个不是叶节点的节点为根,枚举去掉一个叶节点,看根的值是否能在中找到。
什么?只会求树的哈希值?
我们需要思考一种函数,在根变动时,只影响新根和原根两节点的值,这样就可以每枚举到一个点,就算出其为根时的哈希值。因为要先一遍才能换根,所以复杂度为。
并且函数需要很容易去掉某个点的影响。(异或)
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<tr1/unordered_set>
#define ll unsigned long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=5e5+10,p=1e9+7;
std::tr1::unordered_set<ll>Q;
int h[N],cnt,in[N],sz[N],n;
ll Hash[N],ans=1e18;
struct Edge{int to,nxt;}e[N<<1];
il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
il void dfs(re int u,re int fa)
{
sz[u]=1;re ll sum=0;
for(re int i=h[u];i+1;i=e[i].nxt)
{
re int v=e[i].to;
if(v==fa) continue;
dfs(v,u);
sz[u]+=sz[v];
Hash[u]=Hash[u]^(Hash[v]+17);
}
Hash[u]+=sz[u]*p+1;
}
il void dfs1(re int u,re int fa)
{
Q.insert(Hash[u]);
for(re int i=h[u];i+1;i=e[i].nxt)
{
re int v=e[i].to;
if(v==fa) continue;
re ll tmp=(Hash[u]-sz[u]*p-1)^(Hash[v]+17);
tmp+=(n-sz[v])*p+1;
Hash[v]-=sz[v]*p+1;
Hash[v]^=(tmp+17);
Hash[v]+=n*p+1;
sz[v]=n;
dfs1(v,u);
}
}
il void dfs2(re int u,re int fa)
{
for(re int i=h[u];i+1;i=e[i].nxt)
{
re int v=e[i].to;
if(v==fa) continue;
re ll tmp=(Hash[u]-sz[u]*p-1)^(Hash[v]+17);
if(in[v]>1)
{
tmp+=(sz[u]-sz[v])*p+1;
Hash[v]-=sz[v]*p+1;
Hash[v]^=(tmp+17);
Hash[v]+=sz[u]*p+1;
sz[v]=sz[u];
dfs2(v,u);
}
else
{
tmp+=(sz[u]-sz[v])*p+1;
if(Q.count(tmp)) ans=min(ans,1ull*v);
}
}
}
int main()
{
memset(h,-1,sizeof(h));
n=gi();
fp(i,1,n-1)
{
re int u=gi(),v=gi();
add(u,v);add(v,u);
}
dfs(1,0);//计算树A哈希值
dfs1(1,0);//换根算树A哈希值
memset(h,-1,sizeof(h));memset(Hash,0,sizeof(Hash));
fp(i,1,n)
{
re int u=gi(),v=gi();
++in[u];++in[v];
add(u,v);add(v,u);
}
re int i;
for(i=1;i<=n;i++) if(in[i]>1) break;//随便找一个不是叶节点的节点为根
dfs(i,0);//算树B哈希值
dfs2(i,0);//对叶子节点,试去掉它会怎么样;对非叶子节点,进行换根DP
printf("%lld\n",ans);
return 0;
}