BZOJ2368 : Modern Art Plagiarism 树同构

枚举$T_1$的树根，然后DP，设$f[i][j]$表示$T_1$的子树$i$是否存在包括i的连通子树与$T_2$的子树$j$同构。

若$j$是叶子，那么显然可以。

若$deg_i<deg_j$，那么显然不可以。

否则将$i$与$j$所有互相同构的儿子之间连边，二分图匹配判断是否存在完美匹配即可。

#include<cstdio>

#include<algorithm>

const int N=105;

int T,C,n,m,o,i,j,k,x,y;

int g[N],v[N<<1],nxt[N<<1],ed,f[N],d[N],deg[N],q[N];

int G[N],V[N<<1],NXT[N<<1],ED,F[N],D[N],DEG[N],Q[N];

bool dp[N][N],ok[N][N],b[N];int p[N];

inline bool cmp(int x,int y){return d[x]>d[y];}

inline bool CMP(int x,int y){return D[x]>D[y];}

inline void add(int*g,int*v,int*nxt,int&ed,int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}

void dfs(int x,int y,int*f,int*d,int*deg,int*g,int*v,int*nxt){

  f[x]=y,d[x]=d[y]+1;deg[x]=0;

  for(int i=g[x];i;i=nxt[i])if(v[i]!=y)deg[x]++,dfs(v[i],x,f,d,deg,g,v,nxt);

}

bool find(int x){

  for(int i=1;i<=o;i++)if(!b[i]&&ok[x][i]){

    b[i]=1;

    if(!p[i]||find(p[i]))return p[i]=x,1;

  }

  return 0;

}

inline void DP(int x,int y){

  dp[x][y]=0;

  if(deg[x]<DEG[y])return;

  if(!DEG[y]){dp[x][y]=1;return;}

  int n=o=0,i,j,cnt=0;

  static int A[N],B[N];

  for(i=g[x];i;i=nxt[i])if(v[i]!=f[x])A[++n]=v[i];

  for(i=G[y];i;i=NXT[i])if(V[i]!=F[y])B[++o]=V[i];

  for(i=1;i<=n;i++)for(j=1;j<=o;j++)ok[i][j]=dp[A[i]][B[j]];

  for(i=1;i<=o;i++)p[i]=0;

  for(i=1;i<=n;i++){

    for(j=1;j<=o;j++)b[j]=0;

    if(find(i)){

      cnt++;

      if(cnt==o){dp[x][y]=1;return;}

    }

  }

}

bool solve(){

  scanf("%d",&n);

  for(ed=0,i=1;i<=n;i++)g[i]=0,q[i]=i;

  for(i=1;i<n;i++)scanf("%d%d",&x,&y),add(g,v,nxt,ed,x,y),add(g,v,nxt,ed,y,x);

  scanf("%d",&m);

  for(ED=0,i=1;i<=m;i++)G[i]=0;

  for(i=1;i<m;i++)scanf("%d%d",&x,&y),add(G,V,NXT,ED,x,y),add(G,V,NXT,ED,y,x);

  dfs(1,0,F,D,DEG,G,V,NXT);

  for(i=1;i<=m;i++)Q[i]=i;

  std::sort(Q+1,Q+m+1,CMP);

  for(i=1;i<=n;i++){

    dfs(i,0,f,d,deg,g,v,nxt);

    std::sort(q+1,q+n+1,cmp);

    for(j=1;j<=n;j++)for(k=1;k<=m;k++)DP(q[j],Q[k]);

    if(dp[i][1])return 1;

  }

  return 0;

}

int main(){

  for(scanf("%d",&T);T--;puts(solve()?"YES":"NO"));

  return 0;

}