[WC2010]重建计划

又一道长链剖分好题。

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

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

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

于是乎问题就转变成了求树上权值和最大的链，这时马上想到我们以前做过的一道题P2993 [FJOI2014]最短路径树问题题解，我已经在这道题的题解中把需要的思想讲明白了，如果你还不会那道题，最好先去做一做。对于这道题，就是开一个标记数组\(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]重建计划长链剖分

[WC2010]重建计划

最新文章

热门文章

巴特西

[WC2010]重建计划 长链剖分

[WC2010]重建计划

最新文章

热门文章

[WC2010]重建计划长链剖分