回复 @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，你们的代码完全看不懂

只会自己的乱YY的启发式并查集，QAQ，Orz 会左偏树的大佬

不用树剖呀！

刚进前500QAQ

第一道topo判环留念~
第一次手写快读留念~
1A留念~

第一次加题QAQ

回复 @Hale :
谢了！

。。。

水题就是快

时隔三个月后，终于验题了，还是我太弱了，hs Orz