【BZOJ3197】[Sdoi2013]assassin树同构+动态规划+KM

HINT

题意：给你两棵同构的树，每个节点都有权值0/1，现在想改变第一棵树中部分点的权值，使得两棵树对应的节点权值相同，问最少改变多少节点。

题解：先考虑树hash+树形DP。树hash的方法同独钓寒江雪。设f[x][y]表示第一棵树中的x节点与第二棵树中的y节点对应时，x的子树中最少改变多少节点。显然只需要处理x和y同构的情况即可。同时，为了满足DP的无后效性，我们应先将所有点按深度从大到小排序，然后用儿子节点的DP值去更新父亲节点的DP值。

但问题是，如果x的一些儿子同构怎么办？虽然每个节点的儿子最多只有10个，但是暴力仍然是不可取的。不过稍微思考一下就能发现这是个二分图最小权匹配问题，直接上KM即可。

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef unsigned long long ull;
const int maxn=710;
int n,m,cnt,rt,rt1,rt2,temp;
int f[maxn][maxn],la[15],lb[15],va[15],vb[15],map[15][15],from[15],siz[maxn],p[maxn];
int dep[maxn],to[maxn<<1],next[maxn<<1],head[maxn],a1[maxn],a2[maxn],vis[maxn];
ull hs[maxn];
vector ch[maxn];
bool cmp1(int a,int b)
{
return hs[a]}
bool cmp2(int a,int b)
{
return (dep[a]==dep[b])?(hs[a]dep[b]);
}
void add(int a,int b)
{
to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;
}
inline int rd()
{
int ret=0,f=1;char gc=getchar();
while(gc<'0'||gc>'9'){if(gc=='-')f=-f;gc=getchar();}
while(gc>='0'&&gc<='9')ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
void getrt(int x,int fa)
{
siz[x]=1;
int flag=0;
for(int i=head[x];i!=-1;i=next[i])if(to[i]!=fa)getrt(to[i],x),siz[x]+=siz[to[i]],flag|=(siz[to[i]]>(n/2));
flag|=(n-siz[x]>(n/2));
if(!flag&&rt1)rt2=x;
if(!flag&&!rt1)rt1=x;
}
void geths(int x)
{
for(int i=head[x];i!=-1;i=next[i])if(!vis[to[i]])vis[to[i]]=1,ch[x].push_back(to[i]);
hs[x]=ch[x].size()+1;
if(!ch[x].size())return ;
for(int i=0;i<(int)ch[x].size();i++)dep[ch[x][i]]=dep[x]+1,geths(ch[x][i]);
sort(ch[x].begin(),ch[x].end(),cmp1);
for(int i=0,j;i<(int)ch[x].size();i++)j=ch[x][i],hs[x]=hs[x]*131+hs[j]*hs[j]*hs[j];
}
int dfs(int x)
{
va[x]=1;
for(int i=0;i{
vb[i]=1;
if(from[i]==-1||dfs(from[i]))
{
from[i]=x;
return 1;
}
}
return 0;
}
int KM()
{
int i,j,k,ret=0;
for(i=0;i{
while(1)
{
memset(va,0,sizeof(va));
memset(vb,0,sizeof(vb));
if(dfs(i))break;
temp=1<<30;
for(j=0;jtemp=min(temp,la[j]+lb[k]-map[j][k]);
for(j=0;jfor(j=0;j}
}
for(i=0;ireturn ret;
}
int main()
{
n=rd();
int i,j,k,l,a,b;
memset(head,-1,sizeof(head));
for(i=1;igetrt(1,0);
for(i=1;i<=n;i++)a1[i]=rd();
for(i=1;i<=n;i++)a2[i]=rd();
if(rt2)rt=++n,add(rt,rt1),add(rt,rt2);
elsert=rt1;
vis[rt]=1,dep[rt]=1,geths(rt);
for(i=1;i<=n;i++)p[i]=i;
sort(p+1,p+n+1,cmp2);
memset(f,-1,sizeof(f));
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(dep[p[i]]!=dep[p[j]]||hs[p[i]]!=hs[p[j]])continue;
m=ch[p[i]].size(),f[p[i]][p[j]]=(a1[p[i]]==a2[p[j]]);
if(!m)continue;
memset(la,0,sizeof(la)),memset(lb,0,sizeof(lb));
memset(from,-1,sizeof(from)),memset(map,-1,sizeof(map));
for(k=0;k{
for(l=0;l{
a=ch[p[i]][k],b=ch[p[j]][l];
if(hs[a]==hs[b])map[k][l]=f[a][b],la[k]=max(la[k],f[a][b]);
}
}
f[p[i]][p[j]]+=KM();
}
}
printf("%d",n-f[rt][rt]);
return 0;
}