WC2010重建计划

2014年12月3日7,5462

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++

 

 

avatar
2 Comment threads
2 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
Kaiser Recent comment authors
  Subscribe  
提醒
春风不识路

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

小轮子

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

Kaiser
Kaiser

n log ^2n

Kaiser
Kaiser

没有对深度排序是n^2的