2025.9.9 nflscsp模拟赛 T4

注意到只有连接不同颜色连通块的边可能记入答案。

我们找的是连接不同颜色连通块的边中权值最小的边。

既然把最短路径转化为了最短边，那是不是有可能是最小生成树。

如果连接 $x,y$ 两点有不在最小生成树上的边，那么它满足权值大于等于它们之间路径上的边，否则可以把大于它的边删掉把它加进去还是连通的。如果记入答案，还要满足 $c_x \ne c_y$，但此时 $x,y$ 最小生成树上路径上的至少某条边记入了答案，那么这条不在最小生成树上的边就没有必要记入答案。

转化到树上后，一条边考虑在父亲处记录答案，可以在每一个父亲处维护一个 $ODT$，是好做的。

我怎么又去想了根号分治，不观察性质下场凄惨。