题目大意

给你一棵树，树上每个节点有$0$或$1$的状态。

用最少的操作次数使得当前状态与目标状态同构。

---

思考历程

首先想到的是找重心。

因为根是不确定的，但重心只会有一个或两个，以重心为根就能方便很多。

如果重心有两个，就将连接它们的边拆成点，让它们分别与这个点相连就好了（重心是连在一起的）。

然后就是树上哈希……

哈希之后就开始了艰辛的思考历程……

于是比赛就结束了。

---

正解

我前面的思考是没有问题的。

后面的该怎么处理？当然是DP啊！

设fi,jf_{i,j}fi,j​表示子树$i$对应子树$j$的最小操作数。

显然如果$i$能匹配$j$，就必须要保证它们的哈希值相等。

但是还会有其它条件，综合起来就是它们祖先的哈希值也相等……

其实为了简化操作，我们再保证它们的深度相等就行了，虽然这并不能保证它们真的能够匹配，但也就算了吧……（我曾试过将完全出去这些冗余状态，但程序跑得更慢了，这意味着数据的这一类冗余状态并不多）

所以可以将点按照深度和哈希值排序，从后往前做。

接下来考虑转移，首先ai xor bja_i \ xor \ b_jai​ xor bj​是一定要加上的、

然后就将各自的子树两两配对，也就是∑fx,y\sum f_{x,y}∑fx,y​，其中$x$是$i$的儿子，$y$是$j$的儿子，而且$x$和$y$哈希值相等。

我们要保证这个东西最小。

于是这就变成了二分图的最小权完备匹配。

题目说每个点的度数小于等于$11$，这意味着看起来能够状压DP。

但实际上，如果不非常用力地开常数，那状压DP是很难卡过去的……（我打了80分）。

于是就可以用费用流或KM算法（因为这题求的是最小权，所以将边权取相反数就可以了）。

时间复杂度为玄学……

---

代码

状压DP

using namespace std;#include 
    
     #include 
     
      #include 
      
       #define N 710#define mod 1000000007inline void get_min(int &a,int b){
    	a>b?a=b:0;}int n;int e[N][11],ne[N];int bz[N][11],nbz;int siz[N];int tmpr[2],cnt,root;void get_siz(int x,int fa){
    	bool is_root=1;	siz[x]=1;	for (int i=0;i
       
        =1;ii=q[--i]){
    		for (int j=i,jj=q[j];j>=1 && dep[ii]==dep[jj] && h[ii]==h[jj];jj=q[--j]){
    			memset(g,63,sizeof g);			g[0][0]=0;			for (int x=0;x
        
         >y&1)							continue;						get_min(g[x+1][k|1<
         
          >x&1) continue; get_min(g[y+1][k|1<
         
        
       
      
     
    

KM算法

using namespace std;#include 
    
     #include 
     
      #include 
      
       #define N 710#define mod 1000000007inline void get_min(int &a,int b){
    	a>b?a=b:0;}int n;int e[N][11],ne[N];int bz[N][11],nbz;int siz[N];int tmpr[2],cnt,root;void get_siz(int x,int fa){
    	bool is_root=1;	siz[x]=1;	for (int i=0;i
       
        =1;ii=q[--i]){
    		for (int j=i,jj=q[j];j>=1 && dep[ii]==dep[jj] && h[ii]==h[jj];jj=q[--j]){
    			calc(ii,jj);			if (ii!=jj)				calc(jj,ii);		}	}	printf("%d\n",f[root][root]);	return 0;}
       
      
     
    

---

总结

想不出来的东西就用网络流吧……