题意可以转化成

任意一棵$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;
}