题意可以转化成
任意一棵$A$中的以$i$为根的树,与$B$树中任意一棵以叶子节点的父亲为根的树(除去此叶节点)相匹配,然后输出这个叶子节点的编号。
如果要做到匹配的话,哈希是一个不错的选择。
考虑如何哈希,
不妨考虑子树大小,
因为如果一棵树与另外一棵树相等,总能找出相匹配的子树。
也就是$f_x=f_x~\operatorname{xor}\limits_{y\in son_x}~(f_y*base+\operatorname{size}_y)$
其中异或有一个很重要的性质可以帮助我们解决此题:
如果这个状态要消失,那么就再异或一遍即可。
然后就是换根树形DP的事情了。
解决好$A$树之后,存一下每一个状态方便进行判断。
$B$树也是类似的操作,求出来之后查找$A$树有没有这个状态就好了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<vector>
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define I inline
#define eps 1e-8
using namespace std;
const int N=1e5+5,M=1e4;
const ull base=8110997;
template<class o>I void qr(o &x)
{
char c=gc;int f=1;x=0;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>I void qw(o x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
namespace Hashmap
{
const int Maxn=198837;
struct edge{int next;ull d;}a[Maxn<<1];int len,last[Maxn];
I void ins(ull d)
{
int x=d%Maxn;
if(!last[x]){a[++len]=(edge){last[x],d};last[x]=len;}
int k;
for(k=last[x];k;k=a[k].next)
{
if(a[k].d==d)return ;
if(!a[k].next)break;
}
a[++len]=(edge){0,d};a[k].next=len;
}
I bool pd(ull d)
{
int x=d%Maxn;
if(!last[x])return 0;
for(int k=last[x];k;k=a[k].next)
if(a[k].d==d)return 1;
return 0;
}
}
struct Tree
{
ull f[N],g[N];int siz[N],n;
struct edge{int y,next;}a[N<<1];int len,last[N];
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
void dfs1(int x,int fa)
{
f[x]=0;siz[x]=1;
for(int k=last[x],y;k;k=a[k].next)
{
if((y=a[k].y)==fa)continue;
dfs1(y,x);
f[x]=f[x]^(f[y]*base+siz[y]);siz[x]+=siz[y];
}
}
void dfs2(int x,int fa)
{
if(fa)g[x]=f[x]^((g[fa]^(f[x]*base+siz[x]))*base+n-siz[x]);
else g[x]=f[x];
for(int k=last[x],y;k;k=a[k].next)
{
if((y=a[k].y)==fa)continue;
dfs2(y,x);
}
}
}A,B;
int deg[N];
int main()
{
int n;qr(n);A.n=n,B.n=n+1;
for(int i=1,x,y;i<n;i++)
qr(x),qr(y),A.ins(x,y),A.ins(y,x);
A.dfs1(1,0);
A.dfs2(1,0);
for(int i=1;i<=n;i++)Hashmap::ins(A.g[i]);
for(int i=1,x,y;i<=n;i++)
qr(x),qr(y),B.ins(x,y),B.ins(y,x),++deg[x],++deg[y];
for(int i=1;i<=n+1;i++)
if(deg[i]>1){B.dfs1(i,0),B.dfs2(i,0);break;}
for(int i=1;i<=n+1;i++)
if(deg[i]==1)
{
int y=B.a[B.last[i]].y;
ull w=B.g[y]^(B.f[i]*base+1);
if(Hashmap::pd(w)){qw(i);puts("");return 0;}
}
return 0;
}
最后一次更新于2020-05-19
0 条评论