2020-2021:teams:i_dont_know_png:multi2020-nowcoder-10

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:i_dont_know_png:multi2020-nowcoder-10 [2020/08/10 22:46]
qxforever 创建
+++ 2020-2021:teams:i_dont_know_png:multi2020-nowcoder-10 [2020/08/11 16:42] (当前版本)
nikkukun add E & J.
@@ 行 13: / 行 13: @@
 ==== 解题思路 ====
+===== 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)$，实际确实能过。
@@ 行 24: / 行 52: @@
 ==== qxforever ====
+最近软工小学期开始了导致昨天睡太晚，中午一睁眼 12:15 ... 前半场人一直都晕晕的，前期丢了很多进度 + 整场写挂了很多发。深刻反省！
 ==== Potassium ====

2020-2021/teams/i_dont_know_png/multi2020-nowcoder-10.1597070784.txt.gz · 最后更改: 2020/08/10 22:46 由 qxforever