[WC2010]重建计划（长链剖分+线段树+分数规划）

比眉伴天荒 2021-11-01 08:44 258阅读 0赞

看到平均值一眼分数规划，二分答案mid，边权变为w\[i\]-mid，看是否有长度在\[L,R\]的正权路径。设f\[i\]\[j\]表示以i为根向下j步最长路径，用长链剖分可以优化到O(1)，查询答案线段树即可，复杂度O(nlog2n)

不知为什么bzoj上RE，luogu上AC，暂时不管了。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    #define lson l,mid,rt<<1
    #define rson mid+1,r,rt<<1|1
    using namespace std;
    const int N=2e5+7;
    int n,L,R,cnt,tot,hd[N],v[N],nxt[N],w[N],son[N],sv[N],dep[N],dfn[N];
    double mid,ans,s[N<<2],val[N],f[N];
    void add(int x,int y,int z){v[++tot]=y,nxt[tot]=hd[x],w[tot]=z,hd[x]=tot;}
    void dfs1(int u,int fa)
    {
        for(int i=hd[u];i;i=nxt[i])
        if(v[i]!=fa)
        {
            dfs1(v[i],u);
            if(dep[v[i]]>=dep[son[u]])son[u]=v[i],sv[u]=w[i];
            if(dep[v[i]]+1>dep[u])dep[u]=dep[v[i]]+1;
        }
    }
    void dfs2(int u,int fa)
    {
        dfn[u]=++cnt;
        if(son[u])dfs2(son[u],u);
        for(int i=hd[u];i;i=nxt[i])if(v[i]!=fa&&v[i]!=son[u])dfs2(v[i],u);
    }
    void update(int k,double v,int l,int r,int rt)
    {
        if(l==r){s[rt]=max(s[rt],v);return;}
        int mid=l+r>>1;
        if(k<=mid)update(k,v,lson);else update(k,v,rson);
        s[rt]=max(s[rt<<1],s[rt<<1|1]);
    }
    double query(int L,int R,int l,int r,int rt)
    {
        if(L<=l&&r<=R)return s[rt];
        int mid=l+r>>1;double ret=-2e9;
        if(L<=mid)ret=max(ret,query(L,R,lson));
        if(R>mid)ret=max(ret,query(L,R,rson));
        return ret;
    }
    void dfs(int u,int fa)
    {
        int id=dfn[u];
        if(son[u])dfs(son[u],u),val[id]=val[id+1]+sv[u]-mid;
        update(id,f[id]=-val[id],1,n,1);
        if(dep[u]>=L)
        {
            double tmp=query(id+L,id+min(dep[u],R),1,n,1);
            ans=max(ans,tmp+val[id]);
        }
        for(int i=hd[u];i;i=nxt[i])
        if(v[i]!=fa&&v[i]!=son[u])
        {
            int idv=dfn[v[i]];
            dfs(v[i],u);
            for(int j=0;j<=dep[v[i]];j++)
            {
                int l=id+max(0,L-j-1),r=id+min(dep[u],R-j-1);
                double tmp=query(l,r,1,n,1);
                ans=max(ans,tmp+val[idv]+val[id]+f[idv+j]+w[i]-mid);
            }
            for(int j=0;j<=dep[v[i]];++j)
            {
                double tmp=val[idv]+f[idv+j]+w[i]-mid-val[id];
                if(tmp>f[id+j+1])update(id+j+1,f[id+j+1]=tmp,1,n,1);
            }
        }
    }
    bool check()
    {
        for(int i=0;i<(N<<2);i++)s[i]=-2e9;
        ans=-2e9,dfs(1,0);
        return ans>=1e-4;
    }
    int main()
    {
        scanf("%d%d%d",&n,&L,&R);
        for(int i=1,x,y,z;i<n;i++)scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);
        dfs1(1,0),dfs2(1,0);
        double l=0,r=1e6;
        while(r-l>1e-4)
        {
            mid=(l+r)/2;
            if(check())l=mid;else r=mid;
        }
        printf("%.3lf",l);
    }

转载于:https://www.cnblogs.com/hfctf0210/p/10905815.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/9502c0c4ddad4338bc7763d8581868f3.png