为时已晚，有机体

为时已晚，有机体

题目大意：给你内向基环树森林，一开始每个点都有个人，每秒所有人会沿着出边走一步，你可以在任意秒取走某个点的人（只能取一次），使得人数最多。现在你要修改尽量少的出边，使得最后你能取出最多的人，以及假设刚刚的答案是k，对每个 t ∈ [ 0 , k ] tin[0,k] t∈[0,k]求修改t条边后，你最多能拿到多少人。 n ≤ 1 0 5 nle10^5 n≤105
题解：
第一问显然是联通快数或者减1。
考虑第二问，假设现在在算 t t t的答案。
首先未必最后形成自环最优。有这样一件事情：t-1的答案对应操作集合不一定是t的答案对应操作集合的子集，但是当固定t的时候，一定存在一种最优解，其余若干连通块都是断掉换边连到某个环上。
那么枚举最后是否形成自环。
若是，则分一开始是否就有自环，然后按照点数排个序就可以了。
否则，考虑枚举当根的环的环长L，那么我们发现断掉某个环的边并到这个长为L的环的时候，我们对两个连通块（后者是断开边的树）分别做L-分层，然后分别求出两个连通块出现次数最多的层数出现的次数，然后加起来。
那么可以对所有连通块，断掉所有环边求贡献，去最大值就是这个连通块对L的贡献，然后取出环长是L的环的连通块中，答案最大的那个，然后把剩下连通块中贡献最大的t个合并上去即可。
最后怎么求断掉一条边求贡献，这个一开始任意钦定删掉某条边算一下，然后依次枚举删哪条边，发现受影响的点只有那条边顶点及其子树中的点，因此总复杂度是连通块大小级别的，因此对所有连通块算贡献是线性的。
优秀的实现（比如桶排）可以做到n乘以根号n（因为不同的环长最多只有根号n种）。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,v) rep(i,0,(int)v.size()-1)
#define lint long long
#define ull unsigned lint
#define db long double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define gc getchar()
#define debug(x) cerr<<#x<<"="<<x
#define sp <<" "
#define ln <<endl
#define clr(a,n) memset(a,0,sizeof(int)*((n)+1))
#define clrv(v) vector<int>().swap(v)
using namespace std;
typedef pair<int,int> pii;
typedef set<int>::iterator sit;
inline int inn()
{int x,ch;while((ch=gc)<'0'||ch>'9');x=ch^'0';while((ch=gc)>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^'0');return x;
}
const int N=100010;
struct edges{int to,pre;
}e[N<<1];int h[N],etop,onc[N],sz[N],p[N],vis[N],ans[N];
vector<int> lst[N],dc[N];
inline int add_edge(int u,int v) { return e[++etop].to=v,e[etop].pre=h[u],h[u]=etop; }
inline int getd(int x,int fa,int dpt,vector<int> &dc,int &sz)
{if(dpt>=(int)dc.size()) dc.resize(dpt+1,0);dc[dpt]++,sz++;for(int i=h[x],y;i;i=e[i].pre)if((y=e[i].to)!=fa&&!onc[e[i].to]) getd(y,x,dpt+1,dc,sz);return 0;
}
inline bool lszcmp(const vector<int> &v1,const vector<int> &v2) { return v1.size()<v2.size(); }
namespace SORT_space{int cnt[N];inline int SORT(int *a,int n){int m=0;rep(i,1,n) m=max(m,a[i]);clr(cnt,m);int t=0;rep(i,1,n) cnt[a[i]]++;rep(i,1,m) rep(j,1,cnt[i]) a[++t]=i;return 0;}
}using SORT_space::SORT;
namespace solve1_space{int _sz[N];inline int solve1(int cnt,int *ans){if(lst[1].size()==1){int s=0,x=0;rep(i,1,cnt) if(lst[i].size()==1&&sz[i]>s) x=i,s=sz[i];swap(lst[1],lst[x]),swap(sz[1],sz[x]);rep(i,1,cnt-1) _sz[i]=sz[i+1];SORT(_sz,cnt-1),reverse(_sz+1,_sz+cnt);s=sz[1];rep(i,1,cnt-1) ans[i]=max(ans[i],s+=_sz[i]);}else{int s=0;rep(i,1,cnt) _sz[i]=sz[i];SORT(_sz,cnt),reverse(_sz+1,_sz+cnt+1);rep(i,1,cnt) ans[i]=max(ans[i],s+=_sz[i]);}return 0;}
}
namespace solve2_space{int cc[N],cnt[N],id[N],Ans,gx[N],val[N];inline int ins(int x) { cc[cnt[x]]--,cc[++cnt[x]]++;if(cc[Ans+1]) Ans++;return 0; }inline int del(int x) { cc[cnt[x]]--,cc[--cnt[x]]++;if(!cc[Ans]) Ans--;return 0; }inline int ins(int x,int k) { while(k--) ins(x);return 0; }inline int del(int x,int k) { while(k--) del(x);return 0; }inline int getgx(vector<int> &p,int cl){int m=(int)p.size(),c=0;Ans=0;rep(i,0,m-1) id[i]=c++;rep(i,0,m-1) { int x=p[i];Rep(j,dc[x]) ins((j+id[i])%cl,dc[x][j]); }int res=Ans;rep(i,0,m-2){int x=p[i];Rep(j,dc[x]) del((j+id[i])%cl,dc[x][j]);id[i]=c++;Rep(j,dc[x]) ins((j+id[i])%cl,dc[x][j]);res=max(res,Ans);}rep(i,0,m-1) { int x=p[i];Rep(j,dc[x]) del((j+id[i])%cl,dc[x][j]); }return res;}inline int solve(int cl,int cnt,int *ans){rep(i,1,cnt) gx[i]=getgx(lst[i],cl);int s=0,x=0,c=0;rep(i,1,cnt) if((int)lst[i].size()==cl&&gx[i]>s) s=gx[i],x=i;val[c=1]=gx[x];rep(i,1,cnt) if(i^x) val[++c]=gx[i];SORT(val+1,cnt-1),reverse(val+2,val+cnt+1);rep(i,1,cnt) val[i]+=val[i-1];rep(i,1,cnt-1) ans[i]=max(ans[i],val[i+1]);return 0;}inline int solve2(int cnt,int *ans){clrv(lst[0]);rep(i,1,cnt) if(lst[i].size()!=lst[i-1].size())solve((int)lst[i].size(),cnt,ans);return 0;}
}
namespace getans0_space{int cnt[N];inline int getans0(vector<int> &p){int t=(int)p.size();clr(cnt,t);Rep(i,p) { int x=p[i];Rep(j,dc[x]) cnt[(i+j)%t]+=dc[x][j]; }int res=0;rep(i,0,t-1) res=max(res,cnt[i]);return res;}
}
int main()
{for(int T=inn();T;T--){int n=inn(),cnt=0;clr(h,n),etop=0,clr(vis,n),clr(onc,n);rep(i,1,n) p[i]=inn(),add_edge(i,p[i]),add_edge(p[i],i);rep(i,1,n) if(!vis[i]){int x=i;while(!vis[x]) vis[x]=1,x=p[x];if(vis[x]==1) for(clrv(lst[++cnt]);!onc[x];x=p[x]) lst[cnt].pb(x),onc[x]=1;for(x=i;vis[x]==1;x=p[x]) vis[x]=2;}sort(lst+1,lst+cnt+1,lszcmp);rep(i,1,cnt) reverse(lst[i].begin(),lst[i].end());rep(i,1,cnt) Rep(j,lst[i]) lst[i][j][onc]=i;clr(sz,cnt);rep(i,1,n) if(onc[i]) clrv(dc[i]),getd(i,0,0,dc[i],sz[onc[i]]);int stp=(lst[1].size()==1?cnt-1:cnt);printf("%dn",stp);clr(ans,stp);rep(i,1,cnt) ans[0]=max(ans[0],getans0_space::getans0(lst[i]));solve1_space::solve1(cnt,ans),solve2_space::solve2(cnt,ans);rep(i,0,stp) printf("%d ",ans[i]);printf("n");}return 0;
}