WC2010重建计划

2014年12月3日3,1192

Description

Input

第一行包含一个正整数N,表示X国的城市个数. 第二行包含两个正整数L和U,表示政策要求的第一期重建方案中修建道路数的上下限 接下来的N-1行描述重建小组的原有方案,每行三个正整数Ai,Bi,Vi分别表示道路(Ai,Bi),其价值为Vi 其中城市由1..N进行标号

Output

输出最大平均估值,保留三位小数

Sample Input

4
2 3
1 2 1
1 3 2
1 4 3

Sample Output

2.500

HINT

20%的数据,N<=5000
30%的数据,N<=100000,原有方案恰好为一条路径
100%的数据,N<=100000,1<=L<=U<=N-1,Vi<=1000000

题解

点分治

对于每个重心,二分一个答案mid

将图中所有边减mid,问题转换为判断是否存在长为x的路径,路径边权和>=0,L<=x<=U

从重心剖开树以后,得到若干棵子树

顺序处理每棵子树,并维护mx[i]表示起点从重心出发,终点在子树内,长度为i的路径边权和最值

对于一棵子树,bfs得其所有路径长度及边权和(起点从重心出发,终点在该子树内)

由于是bfs,所以路径长度是从小到大

mx倒序是从大到小

枚举路径i,维护mx的单调递减队列(dis)

若当前mx+deep[i]>=L则mx加入队尾(维护单调)

若deep[i]+q[l]>U,则l++

 

 

  • 小轮子2017年1月21日 下午2:52 回复

    黄学长,树的点分治+单调队列不是n^2的么

    #1  
  • 春风不识路2017年2月5日 下午7:51 回复

    黄学长,貌似这一题在加了一组数据后您的程序会TLE ρ(・ω・、)

    #2