对于一个$k$，可以二分枚举答案并判断，判断过程可以贪心找最深的点（线段树区间max）+倍增+线段树区间覆盖（清0）来实现，时间复杂度$o(klog_{2}n)$
考虑反过来，暴力枚举答案$x$并求出最少需要的点数量$f(x)=k$，那么$forall f(x)le i< f(x-1)$，都有$i$的答案为$x$
这样的复杂度看似仍然是$o(n^{2}log_{2}n)$，但发现一次贪心至少覆盖$x+1$个点或者已经是最后一次，也就是说最多说单次复杂度为$o(lceil frac{n}{x+1}
ceil log_{2}n)$，累加后通过调和级数保证复杂度为$o(nlog^{ 2
}_{2}n)$
}_{2}n)$
具体线段树的实现上可能比较难，可以再维护一个$tag[k]$表示，可能标记永久化+重新修改来实现会比较方便
另外常数较大，注意线段树常数
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 200005 4 #define L (k<<1) 5 #define R (L+1) 6 #define mid (l+r>>1) 7 struct ji{ 8 int nex,to; 9 }edge[N]; 10 vector<int>v; 11 int E,n,x,head[N],dfn[N],sz[N],sh[N],tr[N<<2],tr2[N<<2],tag[N<<2],f[N][21]; 12 void add(int x,int y){ 13 edge[E].nex=head[x]; 14 edge[E].to=y; 15 head[x]=E++; 16 } 17 void build(int k,int l,int r){ 18 tag[k]=1; 19 if (l==r){ 20 tr[k]=tr2[k]=sh[l]; 21 return; 22 } 23 build(L,l,mid); 24 build(R,mid+1,r); 25 tr[k]=tr2[k]=max(tr[L],tr[R]); 26 } 27 void update(int k,int l,int r,int x,int y,int z){ 28 if ((l>y)||(x>r))return; 29 if ((x<=l)&&(r<=y)){ 30 tag[k]=z; 31 tr[k]=tr2[k]*z; 32 return; 33 } 34 update(L,l,mid,x,y,z); 35 update(R,mid+1,r,x,y,z); 36 tr[k]=max(tr[L],tr[R])*tag[k]; 37 } 38 int query(int k,int l,int r){ 39 if (l==r)return l; 40 if (tr[k]==tr[L])return query(L,l,mid); 41 return query(R,mid+1,r); 42 } 43 void dfs(int k,int fa,int s){ 44 sz[k]=1; 45 sh[k]=s; 46 dfn[k]=++x; 47 f[k][0]=fa; 48 for(int i=1;i<=20;i++)f[k][i]=f[f[k][i-1]][i-1]; 49 for(int i=head[k];i!=-1;i=edge[i].nex){ 50 dfs(edge[i].to,k,s+1); 51 sz[k]+=sz[edge[i].to]; 52 } 53 } 54 int find(int k,int x){ 55 for(int i=0;i<=20;i++) 56 if (x&(1<<i))k=f[k][i]; 57 return k; 58 } 59 int main(){ 60 while (scanf("%d",&n)!=EOF){ 61 E=0; 62 for(int i=1;i<=n;i++)head[i]=-1; 63 for(int i=2;i<=n;i++){ 64 scanf("%d",&x); 65 add(x,i); 66 } 67 x=0; 68 dfs(1,1,1); 69 build(1,1,n); 70 int ans=-1; 71 for(int i=1;i<=n;i++){ 72 v.clear(); 73 while (1){ 74 x=find(query(1,1,n),i); 75 if (x==1)break; 76 v.push_back(x); 77 update(1,1,n,dfn[x],dfn[x]+sz[x]-1,0); 78 } 79 for(int j=0;j<v.size();j++)update(1,1,n,dfn[v[j]],dfn[v[j]]+sz[v[j]]-1,1); 80 ans+=v.size()+1; 81 } 82 printf("%d ",ans); 83 } 84 }