题目
题目链接:https://www.luogu.com.cn/problem/P4323
JYY有两棵树 \(A\) 和 \(B\) :树 \(A\) 有 \(N\) 个点,编号为 \(1\) 到 \(N\) ;树 \(B\) 有\(N+1\) 个节点,编号为 \(1\) 到\(N+1\)。
JYY 知道树 \(B\) 恰好是由树 \(A\) 加上一个叶节点,然后将节点的编号打乱后得到的。他想知道,这个多余的叶子到底是树 \(B\) 中的哪一个叶节点呢?
\(n\leq 10^5\)。
思路
判定树的同构考虑树哈希。
任选一个根节点把第一棵树的哈希求出来,然后可以通过换根求出每一个点作为根的哈希值。把这些值扔到一个 set 中。
然后同样的方法可以求出第二棵树的每一个节点为根的哈希值。对于第二棵树的一个叶子节点,我们只需要判断它作为根的时候,它连接的点得哈希值是否出现在 set 中即可。如果有说明这个叶子可以作为答案。在所有答案中取最小值即可。
时间复杂度 \(O(n\log n)\)。
代码
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=100010;
int n,tot,ans,head[N],deg[N],siz[N];
ull f[N],a[N];
set<ull> s;
struct edge
{
int next,to;
}e[N*2];
void add(int from,int to)
{
e[++tot]=(edge){head[from],to};
head[from]=tot;
}
void dfs1(int x,int fa)
{
siz[x]=f[x]=1;
for (int i=head[x];~i;i=e[i].next)
{
int v=e[i].to;
if (v!=fa)
{
dfs1(v,x); siz[x]+=siz[v];
f[x]+=f[v]*a[siz[v]];
}
}
}
void dfs2(int x,int fa,int typ)
{
if (!typ) s.insert(f[x]);
if (typ && deg[x]==1 && s.find(f[e[head[x]].to])!=s.end()) ans=min(ans,x);
for (int i=head[x];~i;i=e[i].next)
{
int v=e[i].to;
if (v!=fa)
{
f[x]-=f[v]*a[siz[v]]; siz[x]-=siz[v];
f[v]+=f[x]*a[siz[x]]; siz[v]+=siz[x];
dfs2(v,x,typ);
siz[v]-=siz[x]; f[v]-=f[x]*a[siz[x]];
siz[x]+=siz[v]; f[x]+=f[v]*a[siz[v]];
}
}
}
int main()
{
srand(32143057);
scanf("%d",&n);
for (int i=1;i<=n;i++) a[i]=rand();
memset(head,-1,sizeof(head));
for (int i=1,x,y;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
ans=n+1;
dfs1(1,0); dfs2(1,0,0);
memset(head,-1,sizeof(head));
tot=0;
for (int i=1,x,y;i<=n;i++)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
deg[x]++; deg[y]++;
}
dfs1(1,0); dfs2(1,0,1);
cout<<ans;
return 0;
}