故事发生在1486 年的意大利，Ezio 原本只是一个文艺复兴时期的贵族，后来因为家族成员受到圣殿骑士的杀害，决心成为一名刺客。最终，凭借着他的努力和出众的天赋，成为了杰出的刺客大师，他不仅是个身手敏捷的武林高手，飞檐走壁擅长各种暗杀术。刺客组织在他的带领下，为被剥削的平民声张正义，赶跑了原本统治意大利的圣殿骑士首领-教皇亚历山大六世。在他的一生中，经历了无数次惊心动魄、扣人心弦的探险和刺杀。

曾经有一次，为了寻找Altair 留下的线索和装备，Ezio 在佛罗伦萨中的刺客墓穴进行探索。这个刺客墓穴中有许多密室，且任何两个密室之间只存在一条唯一的路径。这些密室里都有一个刺客标记，他可以启动或者关闭该刺客标记。为了打开储存着线索和装备的储藏室，Ezio 必须操作刺客标记来揭开古老的封印。要想解开这个封印，他需要通过改变某些刺客标记的启动情况，使得所有刺客标记与封印密码“看起来一样”。

在这里，“看起来一样”的定义是：存在一种“标记”密室与“密码”密室之间一一对应的关系，使得密室间的连接情况和启动情况相同（提示中有更详细解释）。幸运的是，在Ezio 来到刺客墓穴之前，在Da Vinci 的帮助下，Ezio 已经得知了打开储藏室所需要的密码。

而你的任务则是帮助Ezio 找出达成目标所需要最少的改动标记次数。

参考：

多半是树哈希判同构了。

设$f[u][v]$表示$u$子树和$v$子树同构且同层的情况下$u$子树原标记变动成$v$子树的新标记需要的最少次数。

那么实际上就是枚举$u$和$v$的儿子子树互相匹配，用他们的$f$转移到$f[u][v]$上，很明显这是一个带权二分图匹配的过程，KM是一个很好的选择。

如果要是枚举根来做的话，复杂度就是$O(1331n^2)$过不了，当然如果你使用动态换根的话，虽然我没有想过，但是到目前位置，代码已经快200行了，如果再动态换根的话就要累死了（当然debug就更累了）。

我们有个很妙的性质：取这棵树的重心（如果有两个重心，则将两个重心之间的边上建这个点，取这个点）作为根。

因为我们有一个美妙的结论：两棵树同构，当且仅当以两棵树重心为根的树同构。

（其实我也不知道为什么233可能是此时同构的对是最多的吧……）

#include

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客：+

+++++++++++++++++++++++++++++++++++++++++++