CF1416D Graph and Queries 题解

2026-02-15

题意: 给定一个图,点有权值。有两种操作: 1. 询问从点 $u$ 出发能到达的点中,权值最大的点(并把该权值变为 0)。 2. 删掉图中的某条边。

喵喵题

倒着来做,变成加边和改点权。建立 kruskal 重构树,边权按照查询的顺序。那么每次询问相当于询问一个子树!因为一个加边相当于连接两棵树。

似乎这种连通块相关的,有修改的都和 kruskal 重构树相关。