题目概述

洛谷4292

解题报告

题解里很多点分治，但其实用长链剖分十分的直白。

首先先用01分数规划，二分答案 $mid$ ，然后问题转化为边权为 $w-mid$ 的树上选出一条和 $\ge0$ 且长度在 $[L,R]$ 内的路径。

定义 $f_{i,j}$ 表示 $i$ 子树中到 $i$ 长度为 $j$ 的最大权值路径，则：

1. 长儿子合并上来的时候就是整体加边权。
2. 与短儿子查询答案过程中，枚举短儿子下的路径长度 $j$ ，则显然剩下的路径长度是一个区间 $[l,r]$ ，即区间查询。
3. 短儿子暴力合并，即单点修改。

以上操作均可以用线段树完成，因此考虑用线段树维护长链剖分DP。

由于是整体加边权，因此可以记录全局 $dlt_x$ 表示 $x$ 的增量，这样就可以避免打标记，降低常数。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef double DB;
const int maxn=100000,maxt=maxn<<2;const DB eps=1e-8;

int n,L,R,X[maxn+5],Y[maxn+5],W[maxn+5];
int E,lnk[maxn+5],nxt[(maxn<<1)+5],to[(maxn<<1)+5];DB w[(maxn<<1)+5];
int dep[maxn+5],md[maxn+5],SH[maxn+5],len[maxn+5];
int pl,pos[maxn+5];DB MAX[maxt+5],dlt[maxn+5],ans;

inline void Add(int x,int y,DB z) {to[++E]=y;w[E]=z;nxt[E]=lnk[x];lnk[x]=E;}
void DFS(int x,int pre=0){
    dep[x]=dep[pre]+1;md[x]=dep[x];
    for (int j=lnk[x];j;j=nxt[j])
        if (to[j]!=pre){
            DFS(to[j],x);
            if (md[to[j]]>md[x]) md[x]=md[to[j]],SH[x]=to[j];
        }
    len[x]=len[SH[x]]+1;
}
void Build(int l,int r,int p=1){
    MAX[p]=-1e100;
    if (l==r) return;
    int mid=l+(r-l>>1);
    Build(l,mid,p<<1);Build(mid+1,r,p<<1|1);
}
void Update(int pos,DB k,int l=1,int r=n,int p=1){
    MAX[p]=max(MAX[p],k);
    if (l==r) return;
    int mid=l+(r-l>>1);
    pos<=mid?Update(pos,k,l,mid,p<<1):Update(pos,k,mid+1,r,p<<1|1);
}
DB Ask(int pos,int l=1,int r=n,int p=1){
    if (l==r) return MAX[p];
    int mid=l+(r-l>>1);
    return pos<=mid?Ask(pos,l,mid,p<<1):Ask(pos,mid+1,r,p<<1|1);
}
DB Askmax(int L,int R,int l=1,int r=n,int p=1){
    if (L==l && r==R) return MAX[p];
    int mid=l+(r-l>>1);
    if (R<=mid) return Askmax(L,R,l,mid,p<<1); else if (L>mid) return Askmax(L,R,mid+1,r,p<<1|1);
    else return max(Askmax(L,mid,l,mid,p<<1),Askmax(mid+1,R,mid+1,r,p<<1|1));
}
void DP(int x,int pre=0,bool fl=true){
    if (fl) pos[x]=pl,pl+=len[x];
    dlt[x]=0;
    if (SH[x]){
        for (int j=lnk[x],u;j;j=nxt[j])
            if ((u=to[j])==SH[x]) pos[u]=pos[x]+1,DP(u,x,false),dlt[x]=dlt[u]+w[j];
    }
    Update(pos[x],-dlt[x]);
    for (int j=lnk[x],u;j;j=nxt[j])
        if ((u=to[j])!=pre && u!=SH[x]){
            DP(u,x,true);
            for (int k=max(L-len[x],0);k<len[u] && k+1<=L;k++){
                int l=L-(k+1),r=min(R-(k+1),len[x]-1);
                ans=max(ans,Ask(pos[u]+k)+dlt[u]+w[j]+Askmax(pos[x]+l,pos[x]+r)+dlt[x]);
            }
            for (int k=0;k<len[u];k++) Update(pos[x]+k+1,Ask(pos[u]+k)+dlt[u]+w[j]-dlt[x]);
        }
    int l=L,r=min(R,len[x]-1);
    if (l<=r) ans=max(ans,Askmax(pos[x]+l,pos[x]+r)+dlt[x]);
}
bool check(DB mid){
    E=0;for (int i=1;i<=n;i++) lnk[i]=0;
    for (int i=1;i<n;i++) Add(X[i],Y[i],W[i]-mid),Add(Y[i],X[i],W[i]-mid);
    ans=-1e100;Build(1,n);pl=1;DP(1);
    return ans>=-eps;
}
int main(){
    scanf("%d%d%d",&n,&L,&R);
    DB l=0,r=0;
    for (int i=1;i<n;i++){
        scanf("%d%d%d",&X[i],&Y[i],&W[i]);r=max(r,(DB)W[i]);
        Add(X[i],Y[i],0);Add(Y[i],X[i],0);
    }
    DFS(1);
    for (DB mid=(l+r)/2;r-l>1e-4;mid=(l+r)/2) check(mid)?l=mid:r=mid;
    printf("%.3f\n",l);
    return 0;
}