题：https://ac.nowcoder.com/acm/contest/5675/J
题意：给定T1，T2的有根树，问T1能最少改变多少个节点而变成根节点和T2相同，同时每个节点的父亲节点和T2一样。（要保持变换后T1节点仍是1~n出现1次），题目保证至少有一种可以转化。
分析：考虑dp[i][j]为节点 i 变换为节点 j 的最小代价。i 要转化成 j 的条件就是T1树的 i 节点子树要和T2树的 j 节点子树要同构，这部分用树hash来判断即可。（虽然这部分本人测试过只判断子树大小就可以通过，但这么判断说不通，只有判断是否同构才是正确的）
若同构，则考虑T1树的 i 节点的儿子每一个都和T2树的 j 节点的儿子进行匹配，看最小代价为多少，这部分用费用流来实现（难怪n设这么小）费用为dfs之前计算的dp值。
#include<bits/stdc++.h> using namespace std; #define pb push_back typedef long long ll; const int M=2e5+5; const int inf=0x3f3f3f3f; int book[M+10],prim[M+10],num; void initprim(){ for(int i=2;i<M;i++){ if(!book[i])prim[++num]=i; for(int j=1;j<=num&&1ll*prim[j]*i<M;j++){ book[prim[j]*i]=1; if(i%prim[j]==0) break; } } } struct node{ int v,w,cost,nextt; }e[M]; int mincost; int head[M],cur[M],dis[M],vis[M],tot,s,t; int init(int nn){ s=1,t=nn; for(int i=0;i<=t;i++) head[i]=-1; tot=0; mincost=0; } void addedge(int u,int v,int w,int cost){ e[tot].v=v; e[tot].w=w; e[tot].cost=cost; e[tot].nextt=head[u]; head[u]=tot++; e[tot].v=u; e[tot].w=0; e[tot].cost=-cost; e[tot].nextt=head[v]; head[v]=tot++; } bool bfs(){ for(int i=0;i<=t;i++) dis[i]=inf; queue<int>que; que.push(s); dis[s]=0; while(!que.empty()){ int u=que.front(); que.pop(); vis[u]=0; for(int i=head[u];~i;i=e[i].nextt){ int v=e[i].v; if(e[i].w&&dis[u]+e[i].cost<dis[v]){ dis[v]=dis[u]+e[i].cost; if(!vis[v]){ vis[v]=1; que.push(v); } } } } return dis[t]!=inf; } int dfs(int u,int fl){ if(u==t) return fl; int ans=0; vis[u]=1; for(int i=cur[u];~i;i=e[i].nextt){ int v=e[i].v; if(dis[v]==dis[u]+e[i].cost&&!vis[v]&&e[i].w){ cur[u]=i; int x=dfs(v,min(e[i].w,fl-ans)); e[i].w-=x; e[i^1].w+=x; ans+=x; mincost+=x*e[i].cost; if(ans==fl) break; } } vis[u]=0; return ans; } void MCMF(){ while(bfs()){ for(int i=0;i<=t;i++) cur[i]=head[i]; dfs(s,inf); } } const int N=600; int sz1[N],sz2[N],dp[N][N]; unsigned long long h1[N],h2[N]; vector<int>g1[N],g2[N]; void dfs1(int u){ sz1[u]=1,h1[u]=1; if(!g1[u].size()){ h1[u]=1; return ; } h1[u]=0; for(auto v:g1[u]){ dfs1(v); sz1[u]+=sz1[v]; } for(auto v:g1[u]){ h1[u]+=h1[v]*prim[sz1[v]]; } h1[u]*=sz1[u]; } void dfs2(int u){ sz2[u]=1;h2[u]=1; if(!g2[u].size()){ h2[u]=1; return; } h2[u]=0; for(auto v:g2[u]){ dfs2(v); sz2[u]+=sz2[v]; } for(auto v:g2[u])h2[u]+=h2[v]*prim[sz2[v]]; h2[u]*=sz2[u]; } void solve(int x,int y){ if(h1[x]!=h2[y])return; if(sz1[x]==1){ dp[x][y]=(x!=y); return ; } for(auto l:g1[x]) for(auto r:g2[y]) solve(l,r); init(2+g1[x].size()+g2[y].size()); for(int i=0;i<(int)g1[x].size();i++){ addedge(s,i+2,1,0); for(int j=0;j<(int)g2[y].size();j++){ int tx=g1[x][i],ty=g2[y][j]; addedge(i+2,j+1+g1[x].size()+1,1,dp[tx][ty]); } } for(int i=0;i<(int)g2[y].size();i++) addedge(i+1+g1[x].size()+1,t,1,0); MCMF(); dp[x][y]=min(dp[x][y],mincost+(x!=y)); return ; } int main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); initprim(); int n; cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp[i][j]=n; int rt1,rt2; for(int x,i=1;i<=n;i++){ cin>>x; if(x)g1[x].pb(i); else rt1=i; } for(int x,i=1;i<=n;i++){ cin>>x; if(x)g2[x].pb(i); else rt2=i; } dfs1(rt1),dfs2(rt2); solve(rt1,rt2); cout<<dp[rt1][rt2]<<' '; return 0; }