DeerInZooDivOne

作者：叶珈宁

关键词：DP 树同构 二分图最大权匹配 KM算法

题目简述

给定一棵$n$个节点的树，要求找出两个最大的没有公共点的同构连通块。求这两个连通块的大小。

两个连通块$A,B$同构是指存在一组$A$的点编号集合到$B$的点编号集合的双射$p$，使得如果$A$中的点$u,v$之间有一条边,那么$B$中的点$p(u),p(v)$之间也有一条边。

$n\leq 51$.

算法

假设现在有两棵有根树$T_1,T_2$，$u,v$分别是$T_1,T_2$的根，设$f(u,v)$表示最大的同构连通块大小使得$u,v$是这两个连通块中的对应点（即$p(u)=v$）。那么如何才能求得$f(u,v)$？

设$son(x)$表示$x$的儿子集合，那么如果对所有$a\in son(u),b\in son(v)$都求出了$f(a,b)$，就可以构造一个二分图，左边的点集是$son(u)$,右边的点集是$son(v)$，$a,b$之间的边权是$f(a,b)$，则$f(u,v)$就是这个二分图的最大权匹配+1。

那么回到原问题，把树变成有根树，对于答案的两个连通块，至少有一个连通块的根的子树里没有另一个连通块的点。枚举这个点作为$u$，把$u$和$u$父亲之间的边断开，再枚举它父亲所在的连通块内的一个点作为$v$，计算$f(u,v)$即可。

状态数是$\mathcal{O}(n^3)$的，KM转移的复杂度是$\mathcal{O}(n^3)$的，所以总复杂度是$\mathcal{O}(n^6)$的。