首先二分答案ans, 平均数>=ans <=> 所有人-ans后,sum>=0

题目变成求长度在区间内的最长链

树形dp dp[i][j]表示i的子树里以i为top的长度为j的链max权值 枚举儿子即可转移 转移时顺便更新答案

注意到第一个儿子只用区间加上一个边的权值就可以直接转移 长链剖分 每条链开个线段树维护

O(nlog^2)

#include<bits/stdc++.h>
using std::max;

inline void chmax(double &x,const double &y) { if(x<y)x=y; }
const int N=100010;
const double minmin=1e-8;
int n,L,R;
int t[N];
struct edge
{
    int to,next,len;
}l[N<<1];
int i,j,x,y,k;
int f[N],deep[N],mx[N],son[N],top[N],len_to_f[N];
struct seg
{
    double *mx,*ad;    
    int n;
    void init(int _n)
    {
        n=_n;
        mx=new double [n*4+5];
        ad=new double [n*4+5];
    }
#define Mid (l+r>>1)
#define cl (k<<1)
#define cr (cl+1)
    void add(int k,const double &w)
    {
        mx[k]+=w;ad[k]+=w;
    }
    void down(int k)
    {
        if(ad[k]) { add(cl,ad[k]);add(cr,ad[k]); } 
        ad[k]=0;
    }
    void up(int k)
    {
        mx[k]=max(mx[cl],mx[cr]);
    }
    void change(int x,const double &w)
    {
        int k=1,l=1,r=n;
        while(l!=r)
        {
            down(k);
            if(x<=Mid) { k=cl;r=Mid; }
            else { k=cr;l=Mid+1; } 
        }
        mx[k]=w;
        while(k>>=1) up(k);
    }
    double ans;
    int ql,qr;
    void qiu(int k,int l,int r)
    {
        if(ql<=l&&qr>=r)
        {
            chmax(ans,mx[k]);
            return ;
        }
        if(ql>r||qr<l) return ;
        down(k);
        qiu(cl,l,Mid);
        qiu(cr,Mid+1,r);
    }
    double get(int l,int r)
    {
        ql=l;qr=r;ans=-1e12;
        qiu(1,1,n);
        return ans;
    }
}a[N];
void init(int x)
{
    for(y=x;y;y=son[y]) top[y]=x;
    a[x].init(mx[x]);
}
int st[N],tail;
void dfs(int x,int fr=0,int Deep=0)
{
    st[++tail]=x;
    f[x]=fr;deep[x]=++Deep;

    int i=t[x],y,i0,&c=son[x];
    if(l[i].to==fr) { len_to_f[x]=l[i].len;i=t[x]=l[i].next;} 
    for(;y=l[i].to;i0=i,i=l[i].next)
    if(y==fr)  
    {l[i0].next=l[i].next;len_to_f[x]=l[i].len;} 
    else
    {
        dfs(y,x,Deep);
        if(mx[y]>mx[c]) c=y;
    }

    mx[x]=mx[c]+1;
    if(!c) return ;

    i=t[x];
    if(l[i].to==c)  i=t[x]=l[i].next; 
    for(;y=l[i].to;i0=i,i=l[i].next)
    if(y==c) l[i0].next=l[i].next; 
    else init(y);
}

int head,del,rt;
bool ok(const double &base)
{
    for(head=n;head;--head)
    {
        x=st[head];
        seg &now=a[top[x]];
        del=deep[x]-deep[top[x]]+1;
        now.change(del,0);
        for(i=t[x];y=l[i].to;i=l[i].next)
        {
            for(j=1;j<=a[y].n;++j) 
            if(a[y].get(j,j)+now.get(del+max(L-j,1),del+R-j)>=-minmin) 
             return 1;
            for(j=1;j<=a[y].n;++j) 
            if(a[y].get(j,j)>=now.get(del+j,del+j)+minmin)
             now.change(del+j,a[y].get(j,j)); 
        }
        if(now.get(del+L,del+R)>=-minmin) return 1;
         now.add(1,len_to_f[x]-base);
    }
    return 0;
}

double erfen()
{
    double l=0,r=1e6,mid;
    for(int i=0;i<=40;++i)
    if(ok(mid=(l+r)/2)) l=mid;
    else r=mid;
    return l;
}

int main()
{
    freopen("1.in","r",stdin);freopen("1.out","w",stdout); 
    scanf("%d%d%d",&n,&L,&R);
    int e=n;
    for(i=1;i<n;++i,++e)
    {
        scanf("%d%d%d",&x,&y,&k);
        l[i]=(edge){y,t[x],k};t[x]=i;
        l[e]=(edge){x,t[y],k};t[y]=e;
    }
    dfs(1);init(1);
    printf("%.3lf\n",erfen());
}