题目:
跑原图最小生成树,删的边不在树上答案就是这个,在树上考虑如何连接 \(u\) 的连通块和 \(v\) 的连通块,从非树边中选,脑子空想是类似路径差分 \(\min\),但手画一下其实就是路径 \(\min\)。自己画!
非树边 \((a,b,c)\),在最小生成树上 \(a→b\) 的边区间 \(\min\) 一下 \(c\)(边权下发),查询树边输出当前边 \(\min\)。
跑原图最小生成树,删的边不在树上答案就是这个,在树上考虑如何连接 \(u\) 的连通块和 \(v\) 的连通块,从非树边中选,脑子空想是类似路径差分 \(\min\),但手画一下其实就是路径 \(\min\)。自己画!
非树边 \((a,b,c)\),在最小生成树上 \(a→b\) 的边区间 \(\min\) 一下 \(c\)(边权下发),查询树边输出当前边 \(\min\)。