[做题日记] 02
做题日记 02P1550
要统一操作 , 这类题通常应想到超级源点
删边最小生成树
给出一个图 , 每次询问删去一条边 , 所得最小生成树的长度
这里要想到对于删去原来树上的边 , 可以用不在树上的边替换它
对于一条非树边 (u, v) , 它形成的环u, lca(u, v), v 上的边都可以被替换
但是如果一个点有不止一条这样的边呢
所以考虑按照非树边的权值从小到大排 , 一条边可以管对应的环 , 如果另一个边过来那就没法管了 (它的权值一定小于前面的边)
所以考虑并查集 , 一个点被更新就把它指向 lca(u, v) 上 , 更新答案
最小生成树问题常常可以考虑 lca, 环 等等的东西...
下周开始弄线段树相关 , 分裂合并等等
加油
首先，给出一个图，每次询问删去一条边，所得最小生成树的长度。这种问题通常可以通过使用超级源点来统一操作。
我们可以将原图中的每条非树边替换成不在树上的边。对于一条非树边 (u, v)，它形成了一个环，环上的任意一条边都可以被替换。但是，如果一个点有不止一条这样的边怎么办呢？
可以按照非树边的权值从小到大排列，这样一条边只能管对应的环。如果另一条边过来了，那就不能管了（因为它的权值一定小于前面的边）。因此，我们可以使用并查集来解决这个问题。当一个点被更新时，我们将其指向 lca(u, v)（u和v是该点连接的两个非树边），同时更新答案。
这类最小生成树的问题通常可以考虑使用lca（最近公共祖先）、环等概念来解决。接下来，你可以尝试学习线段树相关内容，比如分裂和合并等操作。加油！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]