自动搬运

查看原文

来自洛谷，原作者为

	dspr **

搬运于2025-08-24 21:58:39，当前版本为作者最后更新于2018-08-15 14:47:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

update:突然发现里面有一个公式鬼畜了，修改一下

没看到有人写长链剖分的题解，于是来发一波。

分数规划就不讲了，其他人讲的很清楚了

然后我们要做的就是在二分答案之后，通过求树上满足要求的最长链来检测答案

首先可以想到一个很暴力的$DP$

设$f_{i,j}$表示以$i$为根的子树，往下走$j$条边的最大权值和

对于一颗子树，可以一边更新数组，一边更新答案。

时间复杂度O($n^2$)

然而这是一个以深度为下标的$DP$

可以考虑用长链剖分优化，做到均摊O(1)的复杂度(后面会讲，有兴趣的可以看看)

然而因为统计答案时要把每个长度的答案都找一遍，如果这样的话时间复杂度还是O($n^2$)，并没有优化的效果，所以我们可以开一颗线段树，像线段树维护重链剖分一样维护长链剖分，这样我们就可以把时间复杂度做到O($n*log\ n$)，与点分治一致，但代码量要小很多，而且也不怕被扫把图卡掉(虽然点分治优化后也不会被卡，但要考虑的越多越易错)

算上二分答案，最终复杂度为O($n*log^2\ n$)

理论上线段树常数应该优于点分治，然而我的常数被点分治吊打了(我是真的弱)。

至于长链剖分

处理一颗树的链上操作时，我们常常我们常常按照子树大小划分重链(也就是重链剖分)，这样每跳一次重链，树的$size$至少乘2，于是可以在$log\ n$的时间内完成一些链上操作，然而有一种划分就是按照最深的子树划分重链，这样虽然不能像重链剖分一样在短时间内完成许多操作(长链剖分的复杂度为O($\sqrt{n}$))，但是这种按深度划分能给我们带来许多优秀的性质。

性质1：所有长链的长度和为$n$，因为长链与重链一样也是互不相交的。

性质2：任意一个节点$x$的$k$级祖先所在长链的长度一定大于或等于$k$(自己想想为什么)

长链剖分有两个经典应用

应用1：在$O(n*log\ n)$的预处理后，$O(1)$求任意一点的$k$级祖先

应用2：优化以深度为下标的树形$DP$

这题就是应用2对吧。那么我就不讲应用1了。

这类以深度为下标的$DP$,我们往往只能暴力for链长更新，然而，对于第一颗子树的信息，我们可以直接继承，为什么，假设对于以$i$为根的子树，要合并第一颗子树$j$时我们要做的仅仅只是将$j$子树的每一个信息复制一遍往后移一位再加上某个权值然后赋给子树$i$,暴力做的话就非常的浪费，会将我们已经得到的信息全部舍弃，那么怎样把这些已经得到的信息利用起来呢。

首先先按深度划分重儿子(至于为什么后面会讲到)，然后对树进行$dfs$，优先遍历重儿子(就跟重链剖分一样，只是划分方式不同),将$dfs$序记录下来，这样我们得到的每一条长链的$dfs$都是连续一段的，然后我们将状态以dfs序记录在数组$f$中，这样我们就会发现，后移一位的操作已经完成了，至于加上一个权值，我们只需要打上一个标记记在另一个数组$g$中，并将重儿子的标记继承，实际上的$f_i$就是$f_i+g_i$,这样同一条长链上的信息可以直接继承，而在轻儿子上的信息我们直接暴力修改，暴力统计答案即可，这样做因为轻儿子一定是某条长链的链头，重儿子的信息直接继承，所以我们只是在每条长链的链头将整条长链遍历一遍，而根据又由于长链互不相交，所以总复杂度为$O(n)$,均摊$O(1)$。

然后看上面加粗字，怎么做呢，以这个节点的$dfs$序为开头,将形如$f_{i,j}$的信息以$f_{dfn_i+j}$的形式保存，便于直接继承，由于继承之后重儿子信息就没用了，所以可以将轻儿子的信息合并。这个时候你应该就能明白为什么要按深度划分链了，因为这样可以使所有轻儿子的信息都能够直接合并上来。

下面是代码，真的比点分治好写。

#include<bits/stdc++.h>
#define lc no<<1
#define rc no<<1|1
#define ls lc,l,mid
#define rs rc,mid+1,r
#define mid ((l+r)>>1)
using namespace std;
const int _=1e6+20;
int a[_],to[_],nex[_],w[_],ww[_],dep[_],son[_],pos[_],n,LL,RR,cnt;
double p,f[_],t[_],ans,g[_];
void clear(int no,int l,int r){
    t[no]=-1e18;
    if(l==r)return;
    clear(ls);clear(rs);
}
void update(int no,int l,int r,int k,double x){
    t[no]=max(t[no],x);
    if(l==r){return;}
    if(k<=mid)update(ls,k,x);
    else update(rs,k,x);
}
double query(int no,int l,int r,int L,int R){
    if(l>R||r<L)return -1e18;
    if(l>=L&&r<=R)return t[no];
    return max(query(ls,L,R),query(rs,L,R));
}
void Dfs(int fa,int u,int W){
    dep[u]=-1;
    for(int i=a[u];i;i=nex[i]){
        int v=to[i];
        if(v==fa)continue;
        Dfs(u,v,w[i]);
        if(dep[u]<dep[v])dep[u]=dep[v],son[u]=v,ww[u]=w[i];
    }
    dep[u]++;
}
void dfs(int fa,int u){
    if(!pos[u])pos[u]=++cnt;
    int pu=pos[u];
    g[pu]=f[pu]=0;
    if(son[u]){
        dfs(u,son[u]);
        g[pu]+=g[pu+1]+ww[u]-p;
        f[pu]=-g[pu];
    }
    update(1,1,n,pu,f[pu]);
    for(int i=a[u];i;i=nex[i]){
        int v=to[i];
        if(v==fa||v==son[u])continue;
        dfs(u,v);int pv=pos[v];
        for(int j=1;j<=dep[v]+1;++j)
            if(LL-j<=dep[u]){
                double xx=query(1,1,n,pu+max(1,LL-j),pu+min(RR-j,dep[u]));
                ans=max(ans,w[i]-p+f[pv+j-1]+g[pv]+g[pu]+xx);
            }
        for(int j=1;j<=dep[v]+1;++j){
            if(w[i]-p+f[pv+j-1]+g[pv]>g[pu]+f[pu+j]){
                f[pu+j]=w[i]-p+f[pv+j-1]+g[pv]-g[pu];
                update(1,1,n,pu+j,f[pu+j]);
            }
        }
    }
    if(dep[u]>=LL)ans=max(ans,g[pu]+query(1,1,n,pu+LL,pu+min(RR,dep[u])));
}
int check(double x){
    clear(1,1,n);p=x;
    ans=-1e18;dfs(0,1);
    return ans>=0;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>LL>>RR;
    for(int i=1,t=0;i<n;++i){
        int u,v,W;cin>>u>>v>>W;
        nex[++t]=a[u];to[t]=v;w[t]=W;a[u]=t;
        nex[++t]=a[v];to[t]=u;w[t]=W;a[v]=t;
    }
    Dfs(0,1,0);
    double l=0,r=1e6;
    while(r-l>1e-5){
        double Mid=(l+r)/2;
        if(check(Mid))l=Mid;
        else r=Mid;
    }
    printf("%.3lf\n",l);
    return 0;
}