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

N<=100000,1<=L<=U<=N-1,Vi<=1000000 新加数据一组 By leoly,但未重测..2016.9.27

题解：

　　好一个扫把树……长见识长见识。

　　显然二分答案+树的点分治。每次遍历一棵子树来得到$dis$数组，表示同一路径数的最大权值，然后再存一个之前遍历子树的桶，含义与$dis$一样，但是要注意从小到大处理每棵子树。扫把树……卡死人。

　　顺便一提，bzoj不会爆栈。

　　（空行比较多，所以显得很长……）

 

1 #define Troy 09/30/2017  2    3 #define inf 0x7fffffff  4    5 #include 
      
         6    7 using namespace std;  8    9 typedef long long ll; 10   11 const int N=500100; 12 const double eps=1e-4; 13   14 inline int read(){ 15     int s=0,k=1;char ch=getchar(); 16     while(ch<'0'|ch>'9')  ch=='-'?k=-1:0,ch=getchar(); 17     while(ch>47&ch<='9')  s=s*10+(ch^48),ch=getchar(); 18     return s*k; 19 } 20   21 struct edges{ 22     int v;ll w;edges *last; 23 }edge[N<<1],*head[N];int cnt; 24   25 inline void push(int u,int v,ll w){ 26     edge[++cnt]=(edges){v,w,head[u]};head[u]=edge+cnt; 27 } 28   29 int n,up,low,tot,top,root,size[N],heavy[N],T[N],Tdis[N],part,from; 30 ll t[N],dis[N]; 31 bool vis[N]; 32 double ans,maxr; 33   34 inline void dfs(int x,int fa,int deep){ 35     size[x]=1; 36     heavy[x]=0; 37     for(edges *i=head[x];i;i=i->last)if(i->v!=fa&&(!vis[i->v])){ 38         dfs(i->v,x,deep+1); 39         size[x]+=size[i->v]; 40         heavy[x]=max(size[i->v],heavy[x]); 41     } 42     heavy[x]=max(heavy[x],tot-size[x]); 43     if(heavy[x]
       
        up)  return ; 49     if(Tdis[lens]!=part){ 50         Tdis[lens]=part; 51         dis[lens]=d; 52     }else 53         dis[lens]=max(dis[lens],d); 54     for(edges *i=head[x];i;i=i->last)    if(i->v!=fa&&(!vis[i->v])){ 55         calc(i->v,x,d+i->w,lens+1); 56     } 57 } 58   59 inline void get_new(int x,int fa,ll d,int lens){ 60     if(lens>up)  return; 61     if(T[lens]!=T[0]) 62         T[lens]=T[0],t[lens]=d; 63     else    64         t[lens]=max(t[lens],d); 65     from=max(from,lens); 66     for(edges *i=head[x];i;i=i->last)    if(i->v!=fa&&(!vis[i->v])){ 67         get_new(i->v,x,d+i->w,lens+1); 68     } 69 } 70   71 int q[N]; 72 double nq[N]; 73   74 inline bool Judge(double x){ 75     int l=0,r=0; 76     int pos=min(up-1,from); 77     bool flag=1; 78     while(pos>=low){ 79         if(T[pos]!=T[0]){    80             pos--;continue; 81         } 82         while(r>l&&nq[r-1]
        
         =0&&i+pos>=low&&T[pos]==T[0]){ 91             while(r>l&&nq[r-1]
         
          up) 97             l++; 98         pos--; 99         if(l
          
           =0)100             return true;101     }102     return false;103 }104  105 struct node{106     int v,w;107     friend bool operator <(node x,node y){108         return size[x.v]
           
            last)if(!vis[i->v]){122 cc++;123 sons[cc].v=i->v;124 sons[cc].w=i->w;125 }126 sort(sons+1,sons+1+cc);127 for(int i=1;i<=cc;i++){128 if(i>1){129 part++;130 calc(sons[i].v,0,sons[i].w,1);131 double l=ans,r=maxr,mid;132 while(l
            
             last) if(!vis[i->v])143 solve(i->v);144 }145 146 int main(){147 n=read();148 low=read(),up=read();149 for(int i=1,u,v,w;i