Luogu

分析

先考虑一个 $\mathcal{O}(n^2)$ 的做法。

先求出以每个节点为根，整棵树的哈希值。

然后，把 $A$ 的所有 $n$ 个哈希值丢到一个 map 里去，然后枚举 $B$ 的每一个叶子节点，判断删掉后的哈希值是否在 map 中即可。

这个算法的主要瓶颈在于 $\mathcal{O}(n^2)$ 求哈希值，我们考虑优化这个过程。

异或满足可减性，很容易抵消掉。所以我们设哈希函数 $f_i=\bigoplus\limits_{j\in Son_i}(f_j\times W+sz_j)$ 。

这样子就可以通过换根 DP 求出以每个点为根时整棵树的哈希值了。

总时间复杂度 $\mathcal{O}(n\log n)$ 。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}
const int N=200001+10;
const int BASE=19491001;

struct Tree {
    int n;

    struct Edge { int v,nxt; } e[N<<1];
    int head[N];

    inline void addEdge(int u,int v) {
        static int cnt=0;
        e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
    }

    unsigned int f[N],h[N];
    int sz[N];

    inline void dfs1(int u,int fa) {
        sz[u]=1;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v; if (v==fa) continue;
            dfs1(v,u),f[u]^=(f[v]*BASE+sz[v]),sz[u]+=sz[v];
        }
    }
    inline void dfs2(int u,int fa) {
        if (!fa) h[u]=f[u];
        else h[u]=f[u]^((h[fa]^(f[u]*BASE+sz[u]))*BASE+(n-sz[u]));
        for (re int i=head[u];i;i=e[i].nxt)
            if (e[i].v!=fa) dfs2(e[i].v,u);
    }
} A,B;

int deg[N];
map<unsigned int,bool> M;

int main() {
    int n=read(); A.n=n,B.n=n+1;
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        A.addEdge(u,v),A.addEdge(v,u);
    }
    for (re int i=1;i<=n;++i) {
        int u=read(),v=read();
        B.addEdge(u,v),B.addEdge(v,u);
        ++deg[u],++deg[v];
    }
    A.dfs1(1,0),A.dfs2(1,0);
    for (re int i=1;i<=n;++i) M[A.h[i]]=1;
    for (re int i=1;i<=n+1;++i)
        if (deg[i]>1) { B.dfs1(i,0),B.dfs2(i,0); break; }
    for (re int i=1;i<=n+1;++i) {
        if (deg[i]>1) continue;
        int v=B.e[B.head[i]].v,w=B.h[v]^(B.f[i]*BASE+1);
        if (M[w]) { printf("%d\n",i); break; }
    }
    return 0;
}