题目链接翻译链接

1 操作相当于有一个年龄为 0 的人已经预先在传销组织里了。

顺序非常难搞。可以看成每个人第一次连边没有贡献。这启发我们把边权直接设为 (也是 ,最后算边权-点权。于是变为一个最大生成树问题。

显然可以 kruskal,枚举边权,枚举以它为权的所有边(边权的子集)。复杂度 。你可能会很惊讶, 是怎么草过这题的呢,小编也很惊讶,但是事实就是这样。

考虑 Boruvka 算法。我们需要做 次以下操作:

考虑如何找点 的最大出边。这里有一个很妙的操作:另一个端点一定是 的子集,如果 中权值最大的点和 不在一个连通块,那么直接取它即可;否则再求一个 和最大值不在一个联通块的最大点。子集DP即可。

代码如下:

彩蛋