题面：

思路：求MST（最小生成树）+树上倍增LCA（树链剖分还不懂orz）

1. 最小生成树的理论依据：无向连通图中任意两点间路径最大权的最小值 = 该图最小生成树中这两点唯一路径中最大权

2. 求最小生成树的方法:

• Kruskal算法（适用于稀疏图）

然而事实是Kruskal还没有自己实现过，把这三题AC掉再说

• Prim算法（适用于稠密图）

本题是完全图Kn，并且Prim算法O（n^2）的复杂度在本题中1<=n<=5000的数据规模里是妥妥的不会TLE.（一般而言，n^2复杂度时，n<=10000较好）

参考链接：

3. 倍增（在线）LCA算法：求Least Common Ancestor

已知一棵树（一般是已知n-1条边及其顶点），每次给出一个询问q，给出两结点a,b之间的最近公共祖先

变式：求树上两结点a,b的距离；求两结点a,b路径最大/小权

参考链接：

 4. 补充：