[做题日记] 02

柿子饼同学

做题日记 02

P1550

要统一操作 , 这类题通常应想到超级源点

删边最小生成树

给出一个图 , 每次询问删去一条边 , 所得最小生成树的长度

这里要想到对于删去原来树上的边 , 可以用不在树上的边替换它

对于一条非树边 (u, v) , 它形成的环  u, lca(u, v), v 上的边都可以被替换

但是如果一个点有不止一条这样的边呢

所以考虑按照非树边的权值从小到大排 , 一条边可以管对应的环 , 如果另一个边过来那就没法管了 (它的权值一定小于前面的边)

所以考虑并查集 , 一个点被更新就把它指向 lca(u, v) 上 , 更新答案

最小生成树问题常常可以考虑 lca, 环 等等的东西...

下周开始弄线段树相关 , 分裂合并等等

加油

FishC

首先，给出一个图，每次询问删去一条边，所得最小生成树的长度。这种问题通常可以通过使用超级源点来统一操作。

我们可以将原图中的每条非树边替换成不在树上的边。对于一条非树边 (u, v)，它形成了一个环，环上的任意一条边都可以被替换。但是，如果一个点有不止一条这样的边怎么办呢？

可以按照非树边的权值从小到大排列，这样一条边只能管对应的环。如果另一条边过来了，那就不能管了（因为它的权值一定小于前面的边）。因此，我们可以使用并查集来解决这个问题。当一个点被更新时，我们将其指向 lca(u, v)（u和v是该点连接的两个非树边），同时更新答案。

这类最小生成树的问题通常可以考虑使用lca（最近公共祖先）、环等概念来解决。接下来，你可以尝试学习线段树相关内容，比如分裂和合并等操作。加油！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。