比赛链接

Solved by .

Solved by nikkukun.

水题不表。

Solved by nikkukun.

给两个 $n \leq 500$ 结点的带标号有根树 $T_1, T_2$，求最少要将第一棵树中多少个标号改变，才能和第二棵树相同。保证两棵树同构。

记 $f(i, j)$ 为将 $T_1$ 的子树 $i$ 和 $T_2$ 的子树 $j$ 匹配最小需要修改的点数，那么每次只需要对 $i$ 和 $j$ 的所有儿子节点找一个完美匹配，使得 $\sum _{u, v \text{ are matched}} f(u, v)$ 最小，这个用 KM 做就行。注意匹配只在两个子树同构的情况下才会进行，可以用树哈希判断一下。

我也不知道复杂度的正确性证明……但是菊花图上 $O(n^3)$，完全 $\sqrt n$ 叉树上 $O(n^{2.5})$，完全二叉树上 $O(n^2)$，实际确实能过。

最近软工小学期开始了导致昨天睡太晚，中午一睁眼 12:15 … 前半场人一直都晕晕的，前期丢了很多进度 + 整场写挂了很多发。深刻反省！