对不起这道题是本蒟蒻搞错意思了，题面的意思是你走过的所有路径中的权值最大，而不是权值和。

回复 @Hale :
但是我给出的样例中，确实是不用经过1的，写了最小生成树不就错了？

回复 @Hale :
意思是题目上说的最大值最小是对于所有人走过的路径和而不是单独每个人最小？

回复 @ShallowDream雨梨 :
假设我们有两个点，x，y,那么他们之间的所有通路理应都是合法的，为保证题目上的所有路径最大值最小，那么在一颗最小生成树，这个最大值一定是最小的；
换一个方向理解，如果这个图不变成树，怎么树上差分啊

这题为什么要先写最小生成树呢？
比如样例
3 3 1
1 2 3
1 3 4
2 3 5
2 3
这个询问不应该是不经过1的吗？但写了最小生成树后路线变成2到1到3了

思路：kruscal求一下最小生成树，然后在新树树上差分即可

回复 @Hale :
这神似树剖的lca真是让在下佩服，orz%%%

回复 @ShallowDream雨梨 :
我只是不会写倍增LCA，和tarjan的LCA，QAQ，Orz

你离AC可能只差十分钟重构

树上差分+最小生成树，是个好题
ps：我本来以为自己已经很能压行了，结果hs神犇比我压得更厉害
1A留念~

楼上上上的大佬写的是求LCA吗？
upd：我还是太蒻了，只会倍增和tarjan求lca，你们的代码完全看不懂

不用树剖呀！