====== 2020牛客暑期多校训练营（第十场） ======

[[https://ac.nowcoder.com/acm/contest/5675 | 比赛链接]]




===== A - Permutation =====

Solved by .

==== 题目描述 ====

==== 解题思路 ====






===== E - Game =====

Solved by nikkukun.

水题不表。




===== J - Identical Tree =====

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)$，实际确实能过。




===== 赛后总结 =====

==== nikkukun ====


==== qxforever ====

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

==== Potassium ====