Description Tar国正在准备每年一次的巡游活动。国王将会在一个城市S里召集人群,沿着城市间的道路进行游览,最终在一个城市T里发表他每年一次的著名演讲。 Tar国有N个城市,由于国家的特殊要求,每两个城市之间存在一条唯一的简单通路。 国王希望借着这个机会视察Tar国的城市建设,因此他提出S到T的距离不能少于L条道路。 同时,国王的私人医生检查了他的身体情况后,断定国王的身体不适合做长途旅行,因此他要求S到T的距离不能多于R条道路。 另外,政府希望跟随国王的人民沿途不仅能看到城市风景,还能看到城市外的美丽乡村。因此每条道路定义了一个魅力值Ci,一条路径的魅力值定义为这条路径的中位数。更详细的说法是这样的: 将路径上所有边的魅力值排序,得到序列{Ai}。假设i=2k+c(0<=c<=1),中位数就是A(k+1)。 你的任务就是求出魅力值最大的路径,并输出这个魅力值。 Input 第一行是三个整数N,L,R,表示Tar国的城市个数、路径的最小和最大长度。 接下来N-1行,每行3个整数Ai,Bi,Ci,表示有一条连接Ai和Bi且魅力值Ci的道路。 Output 仅一行,表示最大的魅力值。如果不存在这样的路径,输出-1。 Sample Input 5 1 4 1 2 1 1 3 4 3 4 7 3 5 2 Sample Output 7 HINT 对于100%的数据:N<=100000,1<=L<=R<=N-1,1<=Ci<=1000000000。 Source 树的分治 基本同http://blog.csdn.net/elijahqi/article/details/79094248 注意我每次二分答案之后把大于等于答案的数改成1反之改成-1 如果做到>=0的数我就退出即可 最后验证答案 如果>=0 l=mid+1;else r=mid-1

 


elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论