CH 6201 走廊泼水节(进阶指南, Kruskal算法构建最小生成树)

《算法竞赛进阶指南》一书共366页，其中介绍了kruskal算法的相关内容。
本题的关键点包括：
1、对于由n个节点构成的树结构，其边的数量为n - 1条。为了将其转换为一个完全图，需要增加 n * (n - 1) / 2 - (n - 1) 条边，从而使得整个图的边总数达到 n * (n - 1) / 2 条。题目要求原树在该完全图中是唯一的最小生成树。
显然，所有新增的边(x, y)的长度必须大于从x点和y点出发的所有其他边；
2、按照kruskal算法进行计算：
在处理边(x, y, z)时，x所在的集合为s[x]，y所在的集合为s[y]。
可以发现，在这两个集合之间相互连接时，共有s[x] * s[y]条可能的边。此时边(x, y, z)必然是最短的一条，否则该树将无法成为唯一的最小生成树；当两个集合合并时，需要添加s[x] * s[y] - 1条新的边（因为s[x]内部的所有节点之间已经两两相连），这些新加入的边的最小长度为z + 1。因此，在最终结果中应加上 ans += (s[x] * s[y] - 1) * (z + 1)

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using na