在此处输入标题

未分类

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<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,B1=157,B2=233,B3=359,p=1e9+7;
unordered_set<ll>Q;
int h[N],cnt;
ll Hash[N];
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 ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
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[x]+=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[y]+17);
      tmp+=(n-sz[v])*p+1;
      Hash[v]-=sz[v]*p+1;
      Hash[v]^=tmp+17;
      Hash[v]+=n*p+1;
      sz[c]=n;
      dfs1(v,u);
    }
}
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);dfs1(1,0);
  memset(h,-1,sizeof(h));memset(Hash,0,sizeof(Hash));
  return 0;
}

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_set>
#define ll long long
#define N 200005
using namespace std;
const ll p=1e9+7;
unordered_set<ll>Q;
ll Hash[N];
int n,D[N],si[N],Ans=1e9;
int TOT,LA[N],NE[N],EN[N];
void ADD(int x,int y)
{
    TOT++;
    EN[TOT]=y;
    NE[TOT]=LA[x];
    LA[x]=TOT;
}
void Ghash(int x,int f)
{
    int i,y;si[x]=1;
    for(i=LA[x];i;i=NE[i])
    {
        y=EN[i];if(y==f)continue;
        Ghash(y,x);si[x]+=si[y];
        Hash[x]=Hash[x]^Hash[y]+17;
    }
    Hash[x]+=si[x]*p+1;
}
void DFS1(int x,int f)
{
    int i,y;Q.insert(Hash[x]);
    for(i=LA[x];i;i=NE[i])
    {
        y=EN[i];if(y==f)continue;
        ll tmp=(Hash[x]-si[x]*p-1)^(Hash[y]+17);
        tmp+=(n-si[y])*p+1;
        Hash[y]-=si[y]*p+1;
        Hash[y]^=tmp+17;
        Hash[y]+=n*p+1;
        si[y]=n;DFS1(y,x);
    }
}
void DFS2(int x,int f)
{
    int i,y;
    for(i=LA[x];i;i=NE[i])
    {
        y=EN[i];if(y==f)continue;
        if(D[y]>1)
        {
            ll tmp=(Hash[x]-si[x]*p-1)^(Hash[y]+17);
            tmp+=(si[x]-si[y])*p+1;
            Hash[y]-=si[y]*p+1;
            Hash[y]^=tmp+17;
            Hash[y]+=si[x]*p+1;
            si[y]=si[x];DFS2(y,x);
        }
        else
        {
            ll tmp=(Hash[x]-si[x]*p-1)^(Hash[y]+17);
            tmp+=(si[x]-si[y])*p+1;
            if(Q.count(tmp))Ans=min(Ans,y);
        }
    }
}
int main()
{
    int i,j,k,x,y;
    scanf("%d",&n);
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        ADD(x,y);ADD(y,x);
    }
    Ghash(1,0);DFS1(1,0);TOT=0;
    memset(LA,0,sizeof(LA));
    memset(Hash,0,sizeof(Hash));
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        D[x]++;D[y]++;
        ADD(x,y);ADD(y,x);
    }
    for(x=1;x<=n;x++)if(D[x]>1)break;
    Ghash(x,0);DFS2(x,0);
    printf("%d",Ans);
}