这种题我都是用树链剖分做的，没想到还有这么简单的方法，ORZ一下！
转自：http://blog.sina.com.cn/s/blog_51cea4040100ss3n.html
给出一棵树，每条边有一边权。
对于任意给定的两点，求，此两点的最短路径上，边权的最大值。
对于下图：
蓝圈中任意一点与红圈中任意一点的路径上的最大边必定是8。
根据这个现象，可以把上述的树重建成如下图所示。
新图的叶子结点为原图的所有结点，内部结点为原图的边权，建边顺序又下小到大。
如图所示：
新图的红色编号为原图的结点编号，蓝色编号为原图的边。
这样，问题就转换为求新图中，任意两个叶子节点的最小公共祖先问题了。