题解 P4292 【[WC2010]重建计划】

· · 题解

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;
}