题目链接：

　　这道题现在已经成为一道板子题了……

　　这是个非常显然的0-1分数规划，可以二分答案之后树分治判定一下。注意树分治的时候如果使用单调队列，需要把所有儿子预先按最大深度排好序，否则会被扫把型的数据卡到\(n^2\log n\)。

　　然后跑得非常慢……于是把二分答案改成了Dinkelbach迭代法。Dinkelbach迭代法就是每次用当前最优解来更新答案的界，跑得比香港记者还快

　　听说这玩意儿复杂度上界是\(\log\)级别的？然而我并不会证……感觉这玩意儿就是玄学啊……

　　二分答案代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)#define maxn 100010#define INF 2147483647#define eps 1e-6using namespace std;typedef long long llg;int n,L,R,siz[maxn],dx[maxn],lc,dep[maxn];int fr[maxn<<1],a[maxn],la,d[maxn],ld,s[maxn];int head[maxn],next[maxn<<1],to[maxn<<1],tt;double c[maxn<<1],lt,dis[maxn];double c1[maxn],c2[maxn],ans;bool vis[maxn];int getint(){ int w=0;bool q=0; char c=getchar(); while((c>'9'||c<'0')&&c!='-') c=getchar(); if(c=='-') c=getchar(),q=1; while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;}bool cmp(int x,int y){return dep[to[x]]
           
            =0) break; } cl=max(cl,lc); for(int j=1;j<=lc;j++) c1[j]=max(c1[j],c2[j]),c2[j]=-1e9; } for(int i=1;i<=cl;i++) c1[i]=-1e9; if(ans+eps>=0){vis[k]=0;return;} for(int i=head[k];i;i=next[i]) if(!vis[to[i]]) work(to[i],i); vis[k]=0;}bool check(double x){ for(int i=1;i<=tt;i++) c[i]+=lt-x; lt=x; ans=-1e9; work(1,0); return ans+eps>=0;}int main(){ File("a"); n=getint(),L=getint(),R=getint(); for(int i=2,u,v;i<=n;i++){ u=getint(),v=getint(); to[++tt]=v;next[tt]=head[u];head[u]=tt; to[++tt]=u;next[tt]=head[v];head[v]=tt; c[tt-1]=c[tt]=getint(); } getroot(1,0); for(int i=1;i<=n;i++) c1[i]=c2[i]=-1e9; double l=0,r=1000000,mid; while(r-l>=1e-4){ mid=(l+r)*0.5; if(check(mid)) l=mid; else r=mid; } printf("%.3lf",l); return 0;}
           
          
         
        
       
      
     

 　　Dinkelbach迭代法代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)#define maxn 100010#define INF 2147483647using namespace std;typedef long long llg;int n,L,R,siz[maxn],dx[maxn],lc,dep[maxn];int fr[maxn<<1],a[maxn],la,d[maxn],ld,s[maxn];int head[maxn],next[maxn<<1],to[maxn<<1],tt;double c[maxn<<1],lt,dis[maxn];double c1[maxn],c2[maxn],ans;bool vis[maxn];int getint(){ int w=0;bool q=0; char c=getchar(); while((c>'9'||c<'0')&&c!='-') c=getchar(); if(c=='-') c=getchar(),q=1; while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;}bool cmp(int x,int y){return dep[to[x]]
           
            ans) ans=x; } } cl=max(cl,lc); for(int j=1;j<=lc;j++) c1[j]=max(c1[j],c2[j]),c2[j]=-1e9; } for(int i=1;i<=cl;i++) c1[i]=-1e9; for(int i=head[k];i;i=next[i]) if(!vis[to[i]]) work(to[i],i); vis[k]=0;}void check(double x){ for(int i=1;i<=tt;i++) c[i]+=lt-x; lt=x; ans=-1e9; work(1,0);}int main(){ File("a"); n=getint(),L=getint(),R=getint(); for(int i=2,u,v;i<=n;i++){ u=getint(),v=getint(); to[++tt]=v;next[tt]=head[u];head[u]=tt; to[++tt]=u;next[tt]=head[v];head[v]=tt; c[tt-1]=c[tt]=getint(); } getroot(1,0); for(int i=1;i<=n;i++) c1[i]=c2[i]=-1e9; double now=0; check(0); while(ans>1e-4) now+=ans,check(now); printf("%.3lf",now); return 0;}
           
          
         
        
       
      
     

 　　实测BZOJ上前一份代码24s+，后一份代码只要5s+