Life Is A Game

 

https://ac.nowcoder.com/acm/contest/24872/H

思路

该题采用kruskal重构树。

kruskal 重构树的特点是将边权化为点权。

当我们使用kruskal求取最小生成树的时候,我们不需要直接生成该树。

每次,我们得到两个点的时候,我们将其连成边时,我们只需要将这棵树两个点提出来,然后我们新加上一个点,且该点的权值是我们原来的边权。

如图所示,我们加边的过程如下。

kruskal

倘若我们再加一条从 B <--> C 相互连接的边的时候。使用如下图所示的方法加边即可。

b<->c

最终,如果我们按照kruskal的方式建立最小生成树的话,不难发现我们所建立的图其实就是一个大根堆。

因此我们可以不断的采用倍增 lca 的方式来寻找第一个符合我们所需要的答案的地方即可。

code

algorithm