正题

题目链接:https://www.luogu.com.cn/problem/P4292

题目大意

给出\(n\)个点的一棵树，然后求长度在\([L,U]\)之间的一条路径的平均权值最大。

解题思路

先上二分\(0/1\)分数规划，然后变成求最长在\([L,U]\)之间的路径。

很经典的点分治问题，但是用线段树会\(T\)，当然可以用单调队列但是我不会。

可以试下上长剖，线段树维护链上每个深度的最大值权值。然后枚举短的那条链的时候在长的那条上面线段树查询就好了。

时间复杂度\(O(n\log^2 n)\)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
const double inf=1e18,eps=1e-6;
struct node{
int to,next;
double w;
}a[N<<1];
int n,L,U,tot,cnt,ls[N];
int dep[N],len[N],son[N],rt[N];
double f[N],nw[N],ans;
struct SegTree{
double w[N<<5];int ls[N<<5],rs[N<<5];
void Change(int &x,int L,int R,int pos,double val){
if(!x)x=++cnt,ls[x]=rs[x]=0,w[x]=-inf;
if(L==R){w[x]=max(val,w[x]);return;}
int mid=(L+R)>>1;
if(pos<=mid)Change(ls[x],L,mid,pos,val);
else Change(rs[x],mid+1,R,pos,val);
w[x]=max(w[ls[x]],w[rs[x]]);return;
}
double Ask(int x,int L,int R,int l,int r){
if(l<L)l=L;if(r>R)r=R;
if(!x||l>r)return -inf;
if(L==l&&R==r)return w[x];
int mid=(L+R)>>1;
if(r<=mid)return Ask(ls[x],L,mid,l,r);
if(l>mid)return Ask(rs[x],mid+1,R,l,r);
return max(Ask(ls[x],L,mid,l,mid),Ask(rs[x],mid+1,R,mid+1,r));
}
}T;
void addl(int x,int y,double w){
a[++tot].to=y;
a[tot].next=ls[x];
ls[x]=tot;a[tot].w=w;
return;
}
void dfs(int x,int fa){
dep[x]=dep[fa]+1;
for(int i=ls[x];i;i=a[i].next){
int y=a[i].to;
if(y==fa)continue;
dfs(y,x);
if(len[y]>len[son[x]])
son[x]=y,nw[x]=a[i].w;
}
len[x]=len[son[x]]+1;
return;
}
void solve(int x,int fa,int t,double k,double dis){
rt[x]=0;
if(son[x])solve(son[x],x,t,k,dis+nw[x]-k);
T.Change(rt[t],dep[t],dep[t]+len[t],dep[x],dis);
for(int i=ls[x];i;i=a[i].next){
int y=a[i].to;
if(y==son[x]||y==fa)continue;
solve(y,x,y,k,dis+a[i].w-k);
for(int j=dep[y];j<=dep[y]+len[y];j++){
f[j]=T.Ask(rt[y],dep[y],dep[y]+len[y],j,j);
ans=max(ans,f[j]+T.Ask(rt[t],dep[t],dep[t]+len[t],2*dep[x]+L-j,2*dep[x]+U-j)-2*dis);
}
for(int j=dep[y];j<=dep[y]+len[y];j++)
T.Change(rt[t],dep[t],dep[t]+len[t],j,f[j]);
}
ans=max(ans,T.Ask(rt[t],dep[t],dep[t]+len[t],dep[x]+L,dep[x]+U)-dis);
return;
}
bool check(double k){
ans=T.w[0]=-inf;cnt=0;
solve(1,1,1,k,0);
return ans>-eps;
}
int main()
{
scanf("%d%d%d",&n,&L,&U);
for(int i=1;i<n;i++){
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
addl(x,y,w);addl(y,x,w);
}
len[0]=-1;dfs(1,1);
double l=0,r=1e6;
while(r-l>eps){
double mid=(l+r)/2.0;
if(check(mid))l=mid;
else r=mid;
}
check(1e6);
printf("%.3lf",(l+r)/2.0);
return 0;
}