@[cyh_qwq](/user/550107)
能不能每次选最短边算联通块总贡献乘以这条边，取最大值
by Paradise_Lost @ 2024-04-26 08:51:17
然后断掉这条边
by Paradise_Lost @ 2024-04-26 08:51:50
@[Paradise_Lost](/user/688649) 忘说了N=3e5,M=1e4
by cyh_qwq @ 2024-04-26 08:53:38
@[cyh_qwq](/user/550107)
这个复杂度也不大吧
by Paradise_Lost @ 2024-04-26 08:54:19
感觉 O(NM) 的复杂度有点悬...
by cyh_qwq @ 2024-04-26 08:55:09
修改可以用线段树，应该是$log$级别的
by Paradise_Lost @ 2024-04-26 08:55:28
每个点影响的是固定的一些块
by Paradise_Lost @ 2024-04-26 08:56:40
@[Paradise_Lost](/user/688649) 那如果是一条链呢?
by cyh_qwq @ 2024-04-26 08:57:21
@[cyh_qwq](/user/550107)
考虑倍增思想，每个点影响log个块，不用线段树都是log的
by Paradise_Lost @ 2024-04-26 08:58:21
@[Paradise_Lost](/user/688649) 所以为什么影响是 $log$ 个块，断开 $n-1$ 条边后不是有 $n$ 个联通块吗?
by cyh_qwq @ 2024-04-26 09:02:14