利用平均数的一个性质：若每个元素都减去x，平均数也减小x，因此可以二分答案Ave，求所有边权值减去Ave后，有无含L~U条边，权值和非负的路径
-> 树的含L~U条边的最长路权值和是否>=0
点分治即可。优化：
1.先求root，再二分，可以避免多次求root
2.先只求经过root的路径的最优Ave，并把它作为 递归求不经过root的路径 时的二分下界
判断该Ave是否可行时，要得到若干不在同一子树上的链，就不从root，而从root的每个子树递归，求出每个子树v[]在每一深度下的最长路径
枚举最优路径在当前子树v[i]下的深度，若为j，则该路径在前1~i-1棵子树中，取边数(即深度)为[L-i,U-i]的最长路径
用数组mx[j]记录前1~i-1棵子树中深度为j的所有路径的最长长度
显然，当子树v[i]确定后，mx[j]数组关于j是单调的，可以用单调队列维护定长区间内的最值
给个图方便理解：
![BZOJ1758 [Wc2010]重建计划（二分答案+点分治+单调队列）](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9pbWdzLzUvNy8wLzkvMTkvNzFmZWYyMDA3ZmRhZTVmMDA2NzYzYTI0NWQ2NzJjZGEuanBl.jpe?w=700 "BZOJ1758 [Wc2010]重建计划（二分答案+点分治+单调队列）")
点分治算法中，树有logN层，每层中的各个点getroot,getd总时间复杂度都是O(N)的，因此算上二分答案，该算法复杂度为：O(NlogNloglim)
因此，不能在操作每个点时使用O(N)的算法，只能在操作每一层时使用均摊O(N)的算法
细节见代码中的注释
#include<stdio.h>
#include<stdlib.h>
double INF=1000000;
double w[200005]={0},d[100005]={0},a[100005]={0},mx[100005]={0};
int v[200005]={0},first[100005]={0},next[200005]={0},size[100005]={0},maxsize[100005]={0},vis[100005]={0},q[100005]={0};
double lim=0.0,ans=0.0,ave;
int n,e=0,L,U,root=0,sum,maxdeep;
int min(int a,int b)
{
if(a<b) return a;
return b;
}
void tj(int x,int y,double z)
{
v[++e]=y;
w[e]=z;
next[e]=first[x];
first[x]=e;
}
void getroot(int x,int fa)
{
int i;
size[x]=1;
maxsize[x]=0;
for(i=first[x];i!=0;i=next[i])
if(v[i]!=fa&&vis[v[i]]==0)
{
getroot(v[i],x);
size[x]+=size[v[i]];
if(maxsize[x]<size[v[i]]) maxsize[x]=size[v[i]];
}
if(maxsize[x]<sum-size[x]) maxsize[x]=sum-size[x];
if(root==0||maxsize[root]>maxsize[x]) root=x;
}
void getd(int x,int fa,int deep)
{
int i;
if(a[deep]<d[x]) a[deep]=d[x];
if(maxdeep<deep) maxdeep=deep;
for(i=first[x];i!=0;i=next[i])
if(v[i]!=fa&&vis[v[i]]==0)
{
d[v[i]]=d[x]+w[i]-ave;
getd(v[i],x,deep+1);
}
}
int judge(int x)
{
int head,tail,i,j,k,endj,Mdeep=0;
mx[0]=a[0]=d[x]=0;
for(i=first[x];i!=0;i=next[i])
if(vis[v[i]]==0)//不从root递归，而从root的每个子树递归，得到若干不在同一子树上的链
{
d[v[i]]=d[x]+w[i]-ave;
maxdeep=0;//记录子树v[i]的最大深度
getd(v[i],x,1);
endj=min(U,maxdeep);//endj:路径在子树v[i]中的深度最大值
head=0;
tail=-1;
for(j=min(U-1,Mdeep);j>=L;j--)//枚举子树v[i]深度前的准备：若之前mx[U-1~L]均为-INF，没必要循环一遍
{
q[++tail]=j;
while(tail>head&&mx[q[tail]]>mx[q[tail-1]])
{
q[tail-1]=q[tail];
tail--;
}
}
for(j=1;j<=endj;j++)//j:枚举路径在子树v[i]中的深度
{
if(L-j>=0)
{
q[++tail]=L-j;
while(tail>head&&mx[q[tail]]>mx[q[tail-1]])
{
q[tail-1]=q[tail];
tail--;
}
}
while(head<=tail&&q[head]>U-j) head++;
if(a[j]+mx[q[head]]>=0)
{
maxdeep=0;
getd(x,0,0);
for(k=1;k<=Mdeep;k++)//别忘了还原mx[],a[]数组
mx[k]=a[k]=-INF;
for(k=Mdeep;k<=maxdeep;k++)//别忘了还原mx[],a[]数组
mx[k]=a[k]=-INF;
return 1;
}
}
for(j=1;j<=maxdeep;j++)
{
if(mx[j]<a[j]) mx[j]=a[j];
a[j]=-INF;
}
if(Mdeep<maxdeep) Mdeep=maxdeep;
}
for(i=1;i<=Mdeep;i++)//mx[]改变的范围是1~maxdeep，因此还原为-INF不需要从1到n循环
mx[i]=a[i]=-INF;
return 0;
}
void getans(int x)
{
double left=ans,right=lim;//二分答案，左闭右开
while(right-left>0.0001)//设置精度
{
ave=(left+right)/2;
if(judge(x)==1) left=ave;
else right=ave;
}
ans=left;
}
void work(int x)
{
int i;
vis[x]=1;
getans(x);//求解经过root的路径的最大满足要求的Ave
for(i=first[x];i!=0;i=next[i])
if(vis[v[i]]==0)
{
sum=size[v[i]];
root=0;
getroot(v[i],x);
if(size[v[i]]>L) work(root);//重要优化
}
}
int main()
{
double z;
int i,x,y;
INF*=INF;
scanf("%d%d%d",&n,&L,&U);
for(i=1;i<n;i++)
{
scanf("%d%d%lf",&x,&y,&z);
tj(x,y,z);
tj(y,x,z);
if(lim<z) lim=z;//二分的右边界
}
for(i=1;i<=n;i++)
mx[i]=a[i]=-INF;
sum=n;
getroot(1,0);
work(root);
printf("%.3lf",ans);
return 0;
}