CF1039D You Are Given a Tree
根号分治好题。
这题可以整体二分，但我太菜了，不会。
根号分治怎么考虑呢？先想想(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
",o[i]);
return 0;
}
鸣谢：@fwat julao