本题 Kruskal 重构树的解法是错误的,因为并不是所有对于非 MST 边 (u,v),MST 上 u-v 的路径上所有边权等于 (u,v) 的边都在 kruskal 重构树的 u-v 的路径上。
考虑以下图(边权均为 1,左边原图,右边重构树,A-B-C 是MST,其中A..C 在重构树上的路径不包括(C,D))
(CD) / \ A--B (AB) D | | / \ | | (BC) A D--C / \ B C