题目描述：
算法标签：点分治，二分，分数规划
思路：
考虑二分出答案，于是对于每一个点把他的权值减去二分出的答案的和相加大于0，且长度适宜，则满足。
于是用点分治判断是否存在这样的路径。
以下代码：
#include<bits/stdc++.h> #define il inline #define db double #define LL long long #define _(d) while(d(isdigit(ch=getchar()))) using namespace std; const int N=2e5+5;const db inf=1e9,eps=1e-4; bool vis[N],flag; vector<int> v[N]; db val[N],mid,len[N],mk[N]; int drt[N],nrt,size,maxdep,d[N],mxd,q[N],top,rt; int n,L,R,head[N],ne[N<<1],to[N<<1],cnt,w[N<<1],sz[N],mx[N]; il int read(){ int x,f=1;char ch; _(!)ch=='-'?f=-1:f;x=ch^48; _()x=(x<<1)+(x<<3)+(ch^48); return f*x; } struct node{ int tl,hd,n,qx[N]; il void init(int size){tl=-1;hd=0;n=size;} il void ins(int x){ if(hd<=tl&&qx[tl]<=x)return; if(hd<tl&&x>n)return; while(len[x]>=len[qx[tl]]&&hd<=tl)tl--; qx[++tl]=x; } il db query(int x){ while(qx[hd]>x&&hd<=tl)hd++; if(hd>tl)return -inf; return len[qx[hd]]; } }Q; il void insert(int x,int y,int z){ ne[++cnt]=head[x];head[x]=cnt; to[cnt]=y;w[cnt]=z; } il void getrt(int x,int fa){ mx[x]=-1;sz[x]=1; for(int i=head[x];i;i=ne[i]){ if(fa==to[i]||vis[to[i]])continue; getrt(to[i],x);sz[x]+=sz[to[i]]; mx[x]=max(mx[x],sz[to[i]]); } mx[x]=max(mx[x],size-sz[x]); if(mx[x]<mx[rt])rt=x; } il void dfs1(int x){ drt[++nrt]=x;vis[x]=1; for(int i=head[x];i;i=ne[i]){ if(vis[to[i]])continue; size=sz[to[i]];rt=0;getrt(to[i],x); dfs1(rt); } } il void dfs(int x,int fa){ mxd=max(mxd,d[x]); for(int i=head[x];i;i=ne[i]){ if(fa==to[i]||vis[to[i]])continue; val[to[i]]=val[x]+(db)w[i]-mid; d[to[i]]=d[x]+1;dfs(to[i],x); } } il void bfs(int s,int from){ q[top=1]=s;mk[s]=from; for(int i=1;i<=top;i++){ for(int j=head[q[i]];j;j=ne[j]){ if(vis[to[j]]||mk[to[j]]==from)continue; mk[q[++top]=to[j]]=from; } } } il void clear(){ for(int i=0;i<=maxdep;i++){ len[i]=-inf;v[i].clear(); } } il void solve(int x){ vis[x]=1;maxdep=0; for(int i=head[x];i;i=ne[i]){ if(vis[to[i]])continue; d[to[i]]=1;mxd=0; val[to[i]]=(db)w[i]-mid; dfs(to[i],x); maxdep=max(maxdep,mxd); v[mxd].push_back(to[i]); } for(int i=1;i<=maxdep;i++){ for(int j=0;j<v[i].size();j++){ top=0;bfs(v[i][j],x);Q.init(maxdep); for(int k=i;k>=L;k--)Q.ins(k); for(int k=1;k<=top;k++){ if(val[q[k]]>=0&&d[q[k]]<=R&&d[q[k]]>=L){flag=1;clear();return;} if(d[q[k]]>R)break; if(d[q[k]]<L)Q.ins(L-d[q[k]]); if(Q.query(R-d[q[k]])+val[q[k]]>=0){flag=1;clear();return;} } for(int k=1;k<=top;k++){ len[d[q[k]]]=max(len[d[q[k]]],val[q[k]]); } } } clear(); } int main() { n=read();L=read();R=read(); for(int i=1;i<n;i++){ int x=read(),y=read(),z=read(); insert(x,y,z);insert(y,x,z); } mx[0]=n+1;size=n;getrt(1,0);dfs1(rt); for(int i=1;i<=n;i++)len[i]=-inf; db l=0,r=1000000,ans=0; while(l+eps<=r){ mid=(l+r)/2.0;flag=0; for(int i=1;i<=n;i++)vis[i]=0,mk[i]=0; for(int i=1;i<=nrt&&!flag;i++)solve(drt[i]); if(flag)l=mid,ans=mid;else r=mid; } printf("%0.3lf ",ans); return 0; }