为啥都是神秘均摊扩展做法啊？？？

Graygoo · 2023-06-08 15:51:00 · 题解

我怀疑 T 宝就是一直在想你们这些均摊做法才没做出来的。实际上有一个没啥思维量的做法，就是首先考虑点权转边权，边权是两个点权最大值，然后条件改成打过的怪数量必须大于等于边权才能走这条边。然后就是老生常谈地建立 kruskal 重构树，在重构树上一条边能走条件就是子树大小大于等于这条边原边权，然后按照这个条件搜下去，能遍历到权值为 0 的点就说明可行，否则显然不可行。

这玩意又好想好写复杂度还是一个 log 的，比官解优秀。