https://zybuluo.com/ysner/note/1177340
题面
有一颗大小为\(n\)的树\(A\)，现加上一个节点并打乱编号，形成树\(B\)，询问加上的节点最后编号是多少?
\(n\leq10^5\)
解析
判断树的同构显然需要树哈希。
可以先将树\(A\)中以每个节点为根的哈希值算出来存进一只\(unordered\_set\)中，
然后在树\(B\)中随便找一个不是叶节点的节点为根，枚举去掉一个叶节点，看根的\(Hash\)值是否能在\(unordered\_set\)中找到。
什么？只会\(O(n^2)\)求树的哈希值？
我们需要思考一种\(Hash\)函数，在根变动时，只影响新根和原根两节点的值，这样就可以每枚举到一个点，就算出其为根时的哈希值。因为要先\(DP\)一遍才能换根，所以复杂度为\(O(2n)\)。
并且函数需要很容易去掉某个点的影响。(异或）
\[Hash_{fa}=(Hash_{son1}+Base)\bigoplus(Hash_{son2}+Base)\bigoplus ...+size_{fa}*p+1\]
一般树哈希还要考虑\(deep\),当然如果你要换根\(DP\)，考虑\(deep\)的影响就没什么用啦。#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;}
[JSOI2016]独特的树叶
原文地址：https://www.cnblogs.com/yanshannan/p/9162385.html