首页 > 其他 > 详细

[WC2010]重建计划

时间:2018-12-08 11:58:56      阅读:188      评论:0      收藏:0      [点我收藏+]

[WC2010]重建计划

LG传送门

又一道长链剖分好题。

这题写点分治的人应该比较多吧,但是我太菜了,只会长链剖分。

如果你还不会长链剖分的基本操作,可以看看我的长链剖分总结

首先一看求平均值最大,马上想到套个二分,每次把边权变为原来的边权减去二分的答案,看树上有没有长度在\(L\)\(U\)之间的正权链就好了。

于是乎问题就转变成了求树上权值和最大的链,这时马上想到我们以前做过的一道题P3899 [湖南集训]谈笑风生 题解,我已经在这道题的题解中把需要的思想讲明白了,如果你还不会那道题,最好先去做一做。对于这道题,就是开一个标记数组\(b\)记录增量,注意到我们可选的链长是一段区间,考虑用线段树来维护区间最大值。对于每一时刻,线段树上维护的信息都是实际信息减去当前长链顶端的标记值,这样处理元素间的相对大小关系没有改变,于是可以维护区间最大值,且保证了单次转移\(O(logn)\)的复杂度,总的复杂度是\(O(n(logn)^2)\),和点分治一样。

下面的代码没有采用一贯的指针写法,而是用了长链剖分之后的dfs序来记录答案(方便在线段树上统计),事实上二者是等价的。

#include<cstdio>
#include<cctype>
#include<algorithm>
#define R register
#define I inline
#define D double
using namespace std;
const int S=100003,N=200003,M=400003,inf=1e6;
const D eps=1e-5;
char buf[S],*p1,*p2;
I char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,S,stdin),p1==p2)?EOF:*p1++;}
I int rd(){
    R int f=0; R char c=gc();
    while(c<48||c>57) c=gc();
    while(c>47&&c<58) f=f*10+(c^48),c=gc();
    return f;
}
int h[S],s[N],g[N],w[N],d[S],t[S],p[S],q[S],f[S],u[S],c,e,G,n,L,U;
D a[S],b[S],o[M],m;
I void add(int x,int y,int z){s[++c]=h[x],h[x]=c,g[c]=y,w[c]=z;}
void bld(int k,int l,int r){o[k]=-inf;
    if(l==r) return ;
    R int p=k<<1,q=p|1,m=l+r>>1;
    bld(p,l,m),bld(q,m+1,r);
}
void mdf(int k,int l,int r,int x,D v){
    if(l==r){o[k]=max(o[k],v); return ;}
    R int p=k<<1,q=p|1,m=l+r>>1;
    if(x<=m) mdf(p,l,m,x,v);
    else mdf(q,m+1,r,x,v);
    o[k]=max(o[p],o[q]);
}
D qry(int k,int l,int r,int x,int y){
    if(x<=l&&r<=y) return o[k];
    R int p=k<<1,q=p|1,m=l+r>>1; D v=-inf;
    if(x<=m) v=max(v,qry(p,l,m,x,y));
    if(m<y) v=max(v,qry(q,m+1,r,x,y));
    return v;
}
void dfs1(int x,int f){p[x]=f,t[x]=d[x]=d[f]+1;
    for(R int i=h[x],y;i;i=s[i])
        if((y=g[i])^f){dfs1(y,x);
            if(t[y]>t[x]) t[x]=t[y],q[x]=y,u[x]=w[i];
        }
}
void dfs2(int x){if(!f[x]) f[x]=++e;
    R int i,j,y,l=f[x],r,v,k=t[x]-d[x]; D o=-inf; a[l]=b[l]=0;
    if(q[x]) dfs2(q[x]),b[l]=b[l+1]+u[x]-m,a[l]=-b[l];
    for(mdf(1,1,n,l,a[l]),i=h[x];i;i=s[i])
        if((y=g[i])^p[x]&&y^q[x]){dfs2(y),r=f[y];
            for(j=1,v=t[y]-d[y]+1;j<=v;++j)
                if(L-j<=k) o=max(o,a[r+j-1]+b[l]+b[r]+w[i]-m+qry(1,1,n,l+max(1,L-j),l+min(U-j,k)));
            for(j=1;j<=v;++j)
                if(a[r+j-1]+b[r]-b[l]+w[i]-m>a[l+j])
                    a[l+j]=a[r+j-1]+b[r]-b[l]+w[i]-m,mdf(1,1,n,l+j,a[l+j]);
        }
    if(k>=L) o=max(o,b[l]+qry(1,1,n,l+L,l+min(U,k)));
    if(o>=0) G=1;
}
I void chk(){G=0,bld(1,1,n),dfs2(1);}
int main(){
    R int i,x,y,z; D l=0,r=inf;
    for(n=rd(),L=rd(),U=rd(),i=1;i<n;++i)
        x=rd(),y=rd(),z=rd(),add(x,y,z),add(y,x,z);
    for(dfs1(1,0);r-l>eps;G?l=m:r=m) m=(l+r)*0.5,chk();
    printf("%.3lf",l);
    return 0;
}

常数被点分暴踩了

[WC2010]重建计划

原文:https://www.cnblogs.com/cj-chd/p/10086983.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!