题目大意：给定一棵树，求一条长度在L到R的一条路径，使得边权的平均值最大。

题解

树上路径最优化问题，不难想到点分治。

如果没有长度限制，我们可以套上01分数规划的模型，让所有边权减去mid，求一条路径长度非负。

现在考虑有L和R的限制，就是我们在拼接两条路径的时候，每条路径能够匹配的是按深度排序后一段连续区间，我们只需要维护区间最大值。

然后随着深度的单调变化，这个区间在滑动，这就变成了滑动窗口问题。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #define N 100002#define inf 2e9#define Re registerusing namespace std;typedef long long ll;const double eps=1e-4;double mid,ans,ma,deep[N],man[N];int tot,head[N],dp[N],q[N],minl,maxl,size[N],maxdeep,root,sum,n,dep[N],que[N],L,R;bool vis[N],visit[N]; inline ll rd(){    ll x=0;char c=getchar();bool f=0;    while(!isdigit(c)){
   if(c=='-')f=1;c=getchar();}    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}    return f?-x:x;}struct edge{
   int n,to,l;}e[N<<1];inline void add(int u,int v,int l){e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].l=l;}void getsize(int u,int fa){    size[u]=1;    for(Re int i=head[u];i;i=e[i].n)if(e[i].to!=fa&&!vis[e[i].to]){        int v=e[i].to;        getsize(v,u);size[u]+=size[v];    } }inline int mx(int a,int b){
   return a>b?a:b;} inline double maxx(double a,double b){
   return a>b?a:b;}void getroot(int u,int fa){    dp[u]=0;size[u]=1;    for(Re int i=head[u];i;i=e[i].n)if(!vis[e[i].to]&&e[i].to!=fa){        int v=e[i].to;        getroot(v,u);size[u]+=size[v];        dp[u]=mx(dp[u],size[v]);    }    dp[u]=mx(dp[u],sum-size[u]);    if(dp[u]
         
          =1;--i){       int x=que[i];visit[x]=0;       while(p+dep[x]
          
           
            =man[q[R]])R--; q[++R]=x; } while(L<=R&&q[L]+dep[x]
            
             =0)tag=1; } getcalc(v,u); } for(Re int i=1;i<=maxdeep;++i)man[i]=-inf; return tag;}inline void getans(int u){ double l=ans,r=ma; while(r-l>eps){ mid=(l+r)/2.0; if(getcheck(u)){ans=mid;l=mid;}else r=mid; }}void solve(int u){ getans(u);vis[u]=1; for(Re int i=head[u];i;i=e[i].n)if(!vis[e[i].to]){ int v=e[i].to; root=n+1;sum=size[v]; getroot(v,u);//getsize(root,0); solve(root); }}int main(){ n=rd();minl=rd();maxl=rd();int u,v,w; for(int i=1;i<=n;++i)man[i]=-inf; ma=-1e9;ans=1e9; for(Re int i=1;i