题目大意：给定一棵树，求一条长度在L到R的一条路径，使得边权的平均值最大。
题解
树上路径最优化问题，不难想到点分治。
如果没有长度限制，我们可以套上01分数规划的模型，让所有边权减去mid，求一条路径长度非负。
现在考虑有L和R的限制，就是我们在拼接两条路径的时候，每条路径能够匹配的是按深度排序后一段连续区间，我们只需要维护区间最大值。
然后随着深度的单调变化，这个区间在滑动，这就变成了滑动窗口问题。
代码
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define N 100002 #define inf 2e9 #define Re register using 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]<dp[root])root=u; } void getdeep(int u,int fa){ maxdeep=mx(maxdeep,dep[u]); 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;deep[v]=deep[u]+e[i].l-mid;dep[v]=dep[u]+1; getdeep(v,u); } } void getcalc(int u,int fa){ man[dep[u]]=maxx(man[dep[u]],deep[u]); 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;getcalc(v,u); } } inline bool getcheck(int u){ maxdeep=0;bool tag=0; for(Re int i=head[u];i;i=e[i].n)if(!vis[e[i].to]){ int v=e[i].to;deep[v]=e[i].l-mid;dep[v]=1; getdeep(v,u); int h=1,t=1;que[h]=v;visit[v]=1; while(h<=t){ int x=que[h++]; for(int j=head[x];j;j=e[j].n){ int v=e[j].to; if(!vis[v]&&!visit[v]&&v!=u)que[++t]=v,visit[v]=1; } } int p=0;L=1;R=0;q[++R]=0; for(Re int i=t;i>=1;--i){ int x=que[i];visit[x]=0; while(p+dep[x]<maxl&&p<maxdeep){ int x=++p; while(L<=R&&man[x]>=man[q[R]])R--; q[++R]=x; } while(L<=R&&q[L]+dep[x]<minl)L++; if(L<=R&&deep[x]+man[q[L]]>=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<n;++i){ u=rd();v=rd();w=rd();ma=maxx(ma,(double)w);ans=min(ans,(double)w); add(u,v,w);add(v,u,w); } dp[root=n+1]=n;sum=n; getroot(1,0);//getsize(root,0); solve(root); printf("%.3lf",ans); return 0; }