— LCA, 图论, tarjan — 1 min read
GeassCode凭借自己在topcoder上的超凡表现，赢得了国王的喜爱，国王赏赐他一座城池。这座城池里有n个 村子，m条路连接这些村子。坐上城主的GeassCode决定要修路，他打算用最少的代价把所以的村子连在一起。据探子回报，有些村子之间虽然原来没有路 径，但是可以强行的去建一条路。GeassCode想知道，如果强行在某两个村子之间建一条路，最后的总花费是多少？
输入一行三个整数n，m，表示有n个村子，m条可建路径。
2..m+1行，每行3个整数a,b,c（a≠b），表示可以在a和b村庄建一条花费为c的路径。
第m+2行一个整数q，表示有多少个询问。
接下来q个询问，每行3个整数a,b,c（a≠b），表示如果可以另外在a和b村庄建一条花费为c的路径，最终需要多少花费？
对于每个询问输出，输出最少的花费。
4 5 1 2 4 2 3 3 1 4 6 2 4 3 1 3 2 3 3 4 3 1 3 1 1 4 2
8 7 7
n的范围[2,50000],m的范围[2,100000],q的范围[1,50000]。
输入的m条边保证可以把所有村庄连在一起。输入的边权范围[1,106]
张超
解法是如果可以在(u,v)上再加条边，则将最小生成树上的(u,v)节点最短路径中的最大边权与要加上这条边的替换。如果新的花费比旧的花费少，则取新的花费。否则什么也不换，取旧的花费。
如何求树上两点之间的最短路径中的最大边权呢？
可以按照这篇文章所述建一个类似于哈夫曼树，将点作为叶子，边的权值作为祖先构造一个N+N的树：click here
这样写的很容易错，尤其要区分两颗树的规模，我在这上面错了很久。
其实，可以直接在dfs的回溯过程中将子节点的max求出来。这样简单多了。感叹一句：并查集真神奇！