题意
给两个树，大小分别为n和m，现在两棵树各选一些点（包括1），使得这棵树以1号点为根同构（同构就是每个点的孩子数目相同），求最大的同构树。（n, m<=500）
分析
我们从两棵树中各取出一个点，考虑以这两个点为根能得到的最大同构数。
题解
容易得到：
设\(d(i, j)\)表示第一棵树选\(i\)号点，第二棵树选\(j\)号点所能得到的最大同构数。
那么\(d(i, j)\)就是等于从\(i\)这个点的子树选一些点，从\(j\)这个点的子树选一些点，选出的点数目相同，一一匹配，则答案就是这些点的\(\sum d(x, y)\)。
计算这个我们用最大费用流来计算。
同时我们从深度深的向深度浅的进行计算。
#include <bits/stdc++.h>
using namespace std;
const int N=505, M=N*2;
int ed[2][N][N], ecnt[2][N], n[2], ihead[M], cnt=1;
struct E {
int next, from, to, cap, w;
}e[M*M];
void add(int x, int y, int cap, int w) {
e[++cnt]=(E){ihead[x], x, y, cap, w}; ihead[x]=cnt;
e[++cnt]=(E){ihead[y], y, x, 0, -w}; ihead[y]=cnt;
}
int d[M], p[M];
bool spfa(int s, int t, int n) {
static bool vis[M];
static int q[M], fr, ta;
fr=ta=0;
q[ta++]=s;
memset(d, 0x7f, sizeof(int)*(n+1));
d[s]=0;
while(ta!=fr) {
int x=q[fr++];
vis[x]=0;
fr=fr==M?0:fr;
for(int i=ihead[x]; i; i=e[i].next) {
if(!e[i].cap) {
continue;
}
int y=e[i].to;
if(d[y]>d[x]+e[i].w) {
d[y]=d[x]+e[i].w;
p[y]=i;
if(!vis[y]) {
vis[y]=1;
if(d[y]<d[q[fr]]) {
fr=fr==0?M:fr;
q[--fr]=y;
}
else {
q[ta++]=y;
ta=ta==M?0:ta;
}
}
}
}
}
return d[t]!=0x7f7f7f7f;
}
void tadd(int x, int y, int w) {
ed[w][x][ecnt[w][x]++]=y;
ed[w][y][ecnt[w][y]++]=x;
}
int st[2][N][N], scnt[2][N], mxdep;
void dfs(int w, int x, int f, int dep) {
st[w][dep][scnt[w][dep]++]=x;
mxdep=max(dep, mxdep);
int sz=0;
for(int i=0; i<ecnt[w][x]; ++i) {
int y=ed[w][x][i];
if(y==f) {
continue;
}
dfs(w, y, x, dep+1);
ed[w][x][sz++]=y;
}
ecnt[w][x]=sz;
}
int f[N][N];
void work(int x, int y) {
int c1=ecnt[0][x], c2=ecnt[1][y];
int s=c1+c2+1, t=s+1;
memset(ihead, 0, sizeof(int)*(t+1));
cnt=1;
for(int i=1; i<=c1; ++i) {
add(s, i, 1, 0);
}
for(int i=1; i<=c2; ++i) {
add(c1+i, t, 1, 0);
}
for(int i=0; i<c1; ++i) {
for(int j=0; j<c2; ++j) {
int y1=ed[0][x][i], y2=ed[1][y][j];
add(i+1, c1+j+1, 1, -f[y1][y2]);
}
}
int &now=f[x][y];
now=1;
while(spfa(s, t, t)) {
int f=0x7f7f7f7f;
for(int x=t; x!=s; x=e[p[x]].from) f=min(f, e[p[x]].cap);
for(int x=t; x!=s; x=e[p[x]].from) e[p[x]].cap-=f, e[p[x]^1].cap+=f;
now+=-f*d[t];
}
}
void dfs(int dep) {
if(dep<0) {
return;
}
int c1=scnt[0][dep], c2=scnt[1][dep];
for(int i=0; i<c1; ++i) {
for(int j=0; j<c2; ++j) {
work(st[0][dep][i], st[1][dep][j]);
}
}
dfs(dep-1);
}
int main() {
scanf("%d", &n[0]);
for(int i=1; i<n[0]; ++i) {
int x, y;
scanf("%d%d", &x, &y);
tadd(x, y, 0);
}
scanf("%d", &n[1]);
for(int i=1; i<n[1]; ++i) {
int x, y;
scanf("%d%d", &x, &y);
tadd(x, y, 1);
}
dfs(0, 1, 0, 0);
dfs(1, 1, 0, 0);
dfs(mxdep);
printf("%d\n", f[1][1]);
return 0;
}