7.999s超超低空飞过

pd_ds牛逼

最短路径树是什么，只会朴素的A*

天哪怎么这么简单

太简单了QAQ <-划掉！ 3分钟AC
https://www.cnblogs.com/Tidoblogs/p/11420553.html

看这里！ https://www.cnblogs.com/Tidoblogs/p/11420302.html

这一道题的数组开大一点！题目中的那个n<=100有坑！

[size=50]快来快来！水题！[/size]

眼瞎读错题,退役预定

爆栈啊................

三年后帮老学长填了无官方数据的坑

神仙分块，费脑子还费时间

才发现自己FHQ_treap不会判断K大存在。。。。。

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

回复 @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求一下最小生成树，然后在新树树上差分即可