CF1039D You Are Given a Tree

LG传送门

根号分治好题。

这题可以整体二分，但我太菜了，不会。

根号分治怎么考虑呢？先想想\(n^2\)暴力吧。对于每一个要求的\(k\)，一遍dfs直接贪心，能拼成链就直接拼，正确性不用我证明吧。

考虑对于\(k \le \sqrt n\)，直接按照暴力去做，复杂度\(O(n \sqrt n)\)；对于\(k\)从\(\sqrt n+1\)到\(n\)的所有情况，我们发现答案只会在\(\sqrt n\)到\(0\)之间取值（\(k> \sqrt n\)），且是单调不升的，考虑用一个左往右移的指针来维护求解的过程，可以每次求出一段的值，具体来说是这样：先把指针\(i\)指向\(\sqrt n+1\)，然后对于每一个\(i\)，求出\(i\)的答案\(t\)，二分一个与它答案相同的最右边的点，并把这一段的答案更新为\(t\)，这样最多二分\(\sqrt n\)次（最多只有\(\sqrt n\)种答案），每次二分（算上check）的复杂度是\(O(n logn)\)，所以这部分的复杂度就是\(O(n \sqrt n log n)\)，总的复杂度也就是\(O(n \sqrt n log n)\)。

上面把分治的节点默认为\(\sqrt n\)只是为了理解起来直观，事实上复杂度还可以更优。我们发现两块的复杂度还不是很平衡，设分治的节点是\(T\)，那么第一块的复杂度就是\(Tn\)，第二块就是\(\frac{n^2 log n}{T}\)。要使复杂度最低，就应该取\(T=\sqrt{n log n}\)。这样的程序运行效率（理论结果）大概是取\(T\)为\(\sqrt n\)的两倍。

#include<cstdio>

#include<cctype>

#include<cmath>

#define R register

#define I inline

using namespace std;

const int S=100003,N=200003;

char buf[1000000],*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],p[S],d[S],f[S],o[S],n,c,e;

I int max(int x,int y){return x>y?x:y;}

I void add(int x,int y){s[++c]=h[x],h[x]=c,g[c]=y;}

void dfs(int x,int f){

	for(R int i=h[x],y;i;i=s[i])

		if((y=g[i])^f)

			dfs(y,x);

	p[x]=f,d[++e]=x;

}

I int slv(int k){

	R int i,x,r=0;

	for(i=1;i<=n;++i)

		f[i]=1;

	for(i=1;i<=n;++i){

		x=d[i];

		if(p[x]&&(~f[p[x]])&&(~f[x]))

			if(f[x]+f[p[x]]>=k)

				++r,f[p[x]]=-1;

			else

				f[p[x]]=max(f[p[x]],f[x]+1);

	}

	return r;

}

int main(){

	R int q,i,j,x,y,t,l,r,m;

	n=rd(),q=sqrt(n*log(n)/log(2));

	for(i=1;i<n;++i)

		x=rd(),y=rd(),add(x,y),add(y,x);

	dfs(1,0),o[1]=n;

	for(i=2;i<=q;++i)

		o[i]=slv(i);

	for(i=q+1;i<=n;i=l+1){

		l=i,r=n,t=slv(i);

		for(;l<r;slv(m)^t?r=m-1:l=m)

			m=l+r+1>>1;

		for(j=i;j<=l;++j)

			o[j]=t;

	}

	for(i=1;i<=n;++i)

		printf("%d\n",o[i]);

	return 0;

}

鸣谢：@fwat julao