纪念第一个自己写出的黑题...
看一眼就是分数规划，二分答案先套上，二分一个 $mid$ ，把所有边权减 $mid$
然后就变成求树上边数在 $[L,R]$ 范围内的最长链
看到树，看到求链，再看看时间限制，点分治是没得跑了...
关键是考虑具体怎么点分治
每到一个分治节点 $x$ 就考虑所有以它为最浅点的所有链，发现对于两条以它为起点的深度相同的链，我们只要保留最长的长度
所以维护一个桶 $T[i]$ 表示当前深度为 $i$ 的所有以 $x$ 为起点的链的长度最大值，考虑新加入的一个儿子子树 $v$ 如何合并
设 $tmp[i]$ 表示 $v$ 中深度为 $i$（起点是 $x$） 的链的最长长度，考虑 $T$ 和 $tmp$ 的合并：
动态维护两个指针 $ld,rd$ ，分别表示之前的儿子贡献的深度和新加入的儿子贡献的深度
那么有 $ld+rd>=L$ 且 $ld+rd<=R$，考虑枚举 $rd$，使得 $ld$ 跟着变化，并统计合法 $ld$ 的区间内的贡献
通过上面两个式子得到 $ld>=L-rd,ld<=R-rd$ ，即 $ld in [L-rd,R-rd]$
发现 $rd$ 增加 $1$ 那么整个合法区间就整体移一位，并且区间大小不变（不考虑边界），发现这就是个滑动窗口，直接单调队列就完事了
点分树先预处理会快很多
以上就是本题关键思路，具体实现请看代码（代码里有一些细节）
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<vector> using namespace std; typedef long long ll; typedef double db; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+7,inf=1e9+7; const db INF=1e18+7; const double eps=1e-5; int fir[N],from[N<<1],to[N<<1],val[N<<1],cntt; inline void add(int a,int b,int c) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; val[cntt]=c; } int n,L,R; int RT,rt,sz[N],mx[N],tot; bool vis[N]; void find_rt(int x,int fa)//找重心 { sz[x]=mx[x]=1; for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(v==fa||vis[v]) continue; find_rt(v,x); sz[x]+=sz[v]; mx[x]=max(mx[x],sz[v]); } mx[x]=max(mx[x],tot-sz[x]); if(mx[x]<mx[rt]) rt=x; } vector <int> V[N];//存点分树 void build(int x)//预处理点分树 { vis[x]=1; for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(vis[v]) continue; rt=0; tot=sz[v]; find_rt(v,x); V[x].push_back(rt); build(rt); } vis[x]=0; } db tmp[N],mid,T[N]; int tp,Tp,Q[N]; bool flag; void dfs(int x,int fa,int dep,db dis)//枚举子树路径 { tp=max(tp,dep); tmp[dep]=max(tmp[dep],dis);//取max for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(v==fa||vis[v]) continue; dfs(v,x,dep+1,dis+val[i]-mid);//边权减mid } } void work(int x)//求以x为最浅点的最长链 { for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(vis[v]) continue;//枚举儿子 dfs(v,x,1,val[i]-mid); int l=1,r=0; for(int ld=Tp,rd=1;rd<=tp;rd++)//滑动窗口 { while(l<=r && Q[l]>R-rd ) l++; while(ld>=L-rd&&ld>=0) { while(l<=r && T[Q[r]]<=T[ld]) r--; Q[++r]=ld; ld--; } if(l<=r && T[Q[l]]+tmp[rd]>0) { flag=1; break; }//不要直接返回，先把数组清空 } for(int j=1;j<=tp;j++) T[j]=max(T[j],tmp[j]); Tp=max(Tp,tp); for(int j=1;j<=tp;j++) tmp[j]=-INF; tp=0;//注意初始为-INF if(flag) break;//记得先清空再break } for(int i=1;i<=Tp;i++) T[i]=-INF; Tp=0; } void solve(int x)//遍历点分树求最长链 { vis[x]=1; work(x); if(flag) { vis[x]=0; return; } int len=V[x].size(); for(int i=0;i<len;i++) { solve(V[x][i]); if(flag) break; } vis[x]=0; } bool check() { flag=0; solve(RT); return flag; } int main() { mx[0]=inf; n=read(),L=read(),R=read(); for(int i=1;i<=n;i++) T[i]=tmp[i]=-INF;//记得初始化 int a,b,c; db l=INF,r=0,ans=2333; for(int i=1;i<n;i++) { a=read(),b=read(),c=read(); l=min(l,1.0*c),r=max(r,1.0*c); add(a,b,c); add(b,a,c); } tot=n; find_rt(1,0); RT=rt; build(rt); while(l<=r-eps) { mid=(l+r)/2; if(check()) l=mid,ans=mid; else r=mid; } printf("%.3lf ",ans); return 0; }