考虑我们现在树上有k头牛。它们无论散布在树的什么地方，我们总可以移动某些牛，使得这 kkk头牛位于树上的1...k1...k1...k号点。这是非常显然的。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 我们考虑一下，假设位置(x,y)(x,y)(x,y)上的牛是可以在不改动其它位置上的牛的前提下完成交换的，我们把它称作“交换关系”（注意这一名词是针对位置的，不针对位置上到底是哪头牛）。则如果位置(x,y)(x,y)(x,y)与位置(y,z)(y,z)(y,z)都具有“交换关系”，那么，位置(x,z)(x,z)(x,z)也将具有交换关系，因为我们可以先交换位置(x,y)(x,y)(x,y)，再交换(y,z)(y,z)(y,z)，再交换(x,y)(x,y)(x,y)达到交换。换句话说，“交换关系”这种性质，具有可传递性。 则我们如果把“交换关系”看作边的话，它们将会构成许多团（完全图）。设这些团的大小为sis^{i}si，则有kkk头牛时的答案即为 k!∑si\frac{k!}{∑s^{i}} ∑sik! ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 现在我们考虑一下，什么情况下两个位置(x,y)(x,y)(x,y)会具有“交换关系”。 我们不妨想一想，假如你正常地想调换两个位置，你会怎么做？ 现在我们画出图来： 假设我们要交换位置333和555的牛，应该怎么办？ 先把一头牛移到111等待，然后再移动另一头牛。 这启发我们在移动牛时需要在分叉的路径上等待。 也就是说，在一条直线上的牛是不可能交换的。只有有“分叉”的地方才能完成交换。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 什么样的地方不存在“分叉”呢？ 对，一条路径。 我们定义一条“链”为一条路径，使得路径两端的点的度数都不等于222，而链上其它点的度数都等于222。 典型的例子： (3−4−5−6)(3−4−5−6)(3−4−5−6)是一条链，链的两端是子树333与子树666。（实际上，如(2−11−12)(2−11−12)(2−11−12)，(7−9)(7−9)(7−9)都是链）。 来看一下本人亲自拿ipad上的procreate画的抽象草图： （白瞎这么好的软件） 我们设左边子树有AAA个点，右边子树有BBB个点，链上有CCC个点（注意链两段的点既属于链，又属于子树）。 则如果k<(A−1)+(B−1)k<(A−1)+(B−1)k<(A−1)+(B−1)的话，左右子树的点就可以任意交换。 我们感性理解一下： 首先，将所有kkk个点全都移到AAA子树或BBB子树中。则此时链上没有任何点（包括链两段），并且两颗子树中至少有一个空隙。 则这一个空隙，就可以成为我们之前提到的“等待”处，进行交换。 而只要能完成一次“交换”，则所有位置都可以交换。 （感性理解一下吧……严谨的证明我自己都看不懂……） 因为(A−1)+(B−1)=N−C(A−1)+(B−1)=N−C(A−1)+(B−1)=N−C，因此只要k<N−Ck<N−Ck<N−C，两边子树就是可交换的。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 我们考虑删去所有满足上述要求的链上的边。如果从大到小地枚举kkk的话，则删边就会变成加边，就可以使用并查集维护联通块。 考虑对于一坨联通块，有多少个外部节点可以通到它。设ai,bi{a^{i},b^{i}}ai,bi为一条链，使得链的一端在块内，一端在块外。再设Bi{B^{i}}Bi为该链通到的另一端的子树大小。 则能通到该联通块的节点数量为 k−∑(k−Bi−1)k-∑(k-B^{i}-1) k−∑(k−Bi−1) （感性理解：外层用kkk减去的那一大坨，是通不到的点的数量；而内层用kkk减去的，则是对于当前链ai,bi{a^{i},b^{i}}ai,bi来说，能通到联通块内的数量。很明显这样做可能会重复计算，但估计容斥容斥就出来了？） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 我们对于每个联通块，维护它内部的边数量insinsins与它周围被切断的边数outoutout。 则按照实际意义化简，我们得到了 k−(n−ins−1)+(n−k−1)outk−(n−ins−1)+(n−k−1)out k−(n−ins−1)+(n−k−1)out 理解： (n−ins−1)(n−ins−1)(n−ins−1)是外部的点数量（注意insinsins是边数）。我们一开始假设这所有外部的点全部通不到） outoutout是被切断的边数，就是上述的ai,bi{a^{i},b^{i}}ai,bi的数量。乘上(n−k−1)(n−k−1)(n−k−1)是子树中原本的kkk个点数量，再加上需要空出来的那个“等待区”的大小。这是(n−ins−1)(n−ins−1)(n−ins−1)中多减去的那些点。 再套上我们一开始得出的那个公式k!∑si\frac{k!}{∑s^{i}}∑sik! ，则我们得出的那个k−(n−ins−1)+(n−k−1)outk−(n−ins−1)+(n−k−1)outk−(n−ins−1)+(n−k−1)out的式子就是分母中的sis^{i}si。通过预处理阶乘和阶乘的逆元，我们可以直接应用公式。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 最后是统计答案。直接枚举每个联通块即可，不必担心复杂度，因为所有时刻的联通块数量是O(n)O(n)O(n)的（联通块数量与∑链长∑链长∑链长是同级别的）。 复杂度分析：瓶颈在于添加上符合要求的链时，为了方便在kkk递减时直接处理要排序。如果用桶排，复杂度就是O(n)O(n)O(n)的。这里为了图方便，使用的是O(nlogn)O(n log n)O(nlogn)的常规排序。然后是并查集，复杂度是nα(n)nα(n)nα(n)的。这里为了方便，没有按秩合并，因此仍然是O(nlogn)O(nlogn)O(nlogn)的。另一个瓶颈就是维护仍然存在的联通块标号，只能采取平衡树等在O(nlogn)内通过。但是我不小心敲的是vector，理论复杂度是O(n2)O(n^{2})O(n2)的，会被菊花图卡掉，但是没有被卡，大家敲的时候用普通set即可。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 如下是AC代码：

懒得写注释，using namespace std貌似不行，反正我瞎写的，过了就行，所以写的杂乱

#include<bits/stdc++.h> #define ll long long #define re register #define cs const namespace IO{ inline char gc(){ static cs int Rlen=1<<22|1;static char buf[Rlen],*p1,*p2; return (p1p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1p2)?EOF:*p1++; }template<typename T>T get_integer(){ char c;bool f=false;while(!isdigit(c=gc()))f=c=='-';T x=c^48; while(isdigit(c=gc()))x=((x+(x<<2))<<1)+(c^48);return f?-x:x; }inline int gi(){return get_integer<int>();} char obuf[(int)(3e7+7)],*oh=obuf,ch[23]; template<typename T>void print(T a,char c){ if(a<0)a=-a,*oh++='-';int tl=0; do ch[tl]=a%10; while(a/=10); while(tl)*oh=ch[tl--]^48;*oh++=c; }struct obuf_flusher{~obuf_flusher(){fwrite(obuf,1,oh-obuf,stdout);}}Flusher; }using namespace IO; using std::cerr; using std::cout; cs int mod=1e9+7; inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;} inline int dec(int a,int b){return a-b<0?a-b+mod:a-b;} inline int mul(int a,int b){ll r=(ll)ab;return r>=mod?r%mod:r;} inline void Inc(int &a,int b){a+=b-mod;a+=a>>31&mod;} inline void Dec(int &a,int b){a-=b;a+=a>>31&mod;} inline void Mul(int &a,int b){a=mul(a,b);} inline int po(int a,int b){int r=1;for(;b;b>>=1,Mul(a,a))if(b&1)Mul(r,a);return r;} inline void ex_gcd(int a,int b,int &x,int &y){ if(!b){x=1,y=0;return;}ex_gcd(b,a%b,y,x);y-=a/bx; }inline int Inv(int a){static int x,y;ex_gcd(mod,a,y,x);return x+(x>>31&mod);} cs int N=1e5+7; struct atom{ int u,v,su,sv,sm; atom(int _u,int _v,int _su,int _sv) :u(_u),v(_v),su(_su),sv(_sv),sm(su+sv-2){} }; int n,rt,sz[N]; std::vector<int> G[N]; int fac[N],ifc[N]; std::vector<atom> path; void dfs(int u,int p){ for(int v:G[u]) if(v!=p)dfs(v,u),sz[u]+=sz[v]; ++sz[u]; } void get_path(int u,int p,int up,int siz){ if(G[u].size()!=2){ if(up) path.push_back((atom){u,up,sz[u],siz}); for(int v:G[u])if(v!=p) get_path(v,u,u,n-sz[v]); }else { for(int v:G[u])if(v!=p) get_path(v,u,up,siz); } } int pr[N],nx[N],fa[N]; void del(int u){ pr[nx[u]]=pr[u]; nx[pr[u]]=nx[u]; } int f[N],g[N],ans[N]; int gf(int u){ while(u!=fa[u]) u=fa[u]=fa[fa[u]]; return u; } void merge(cs atom &t){ int u=gf(t.u),v=gf(t.v); f[u]+=f[v]-2,g[u]+=g[v]-t.sm,fa[v]=u; } void Main(){ n=gi(); for(int re i=1;i<n;++i){ int u=gi(),v=gi(); G[u].push_back(v); G[v].push_back(u); } for(int re i=fac[0]=1;i<=n;++i) fac[i]=mul(fac[i-1],i); ifc[n]=Inv(fac[n]); for(int re i=n;i;--i) ifc[i-1]=mul(ifc[i],i); for(rt=1;G[rt].size()==2;++rt); dfs(rt,0);get_path(rt,0,0,0); for(int re i=0;i<=n+1;++i) pr[i]=i-1,nx[i]=i+1; for(int re i=1;i<=n;++i) if(G[i].size()==2u)del(i); else fa[i]=i; for(auto &t:path){ ++f[t.u],f[t.v]; g[t.u]+=t.su-1; g[t.v]+=t.sv-1; } std::sort(path.begin(),path.end(), [](cs atom &a,cs atom &b){return a.sm>b.sm;}); auto nw=path.begin(); for(int re k=n-1;k;--k){ while(nw!=path.end()&&nw->sm>k) merge(*nw); ans[k]=fac[k]; for(int re i=nx[0];i<=n;i=nx[i]){ if(gf(i)!=i)del(i); else { int t=k-k*f[i]+g[i]; Mul(ans[k],ifc[t]); } } }for(int re i=1;i<n;++i) print(ans[i],'\n'); print(fac[n],'\n'); } inline void file(){ #ifdef zxyoi freopen("circus.in","r",stdin); #endif }signed main(){file();Main();return 0;}

“简单”

#include<bits/stdc++.h> using namespace std; const int mod=1e9+7; int ksm(int x,int y){ int z=1; for(;y;x=1llxx%mod,y>>=1)if(y&1)z=1llzx%mod; return z; } int n,fac[100100],inv[100100],res[100100]; vector<int>g[100100],key; struct dsu{ int fa,ins,out; }a[100100]; void init(){ for(int i=1;i<=n;i++)if(g[i].size()!=2)a[i].fa=i,a[i].out=g[i].size(),key.push_back(i); fac[0]=1; for(int i=1;i<=n;i++)fac[i]=1llfac[i-1]i%mod; inv[n]=ksm(fac[n],mod-2); for(int i=n-1;i>=0;i--)inv[i]=1llinv[i+1](i+1)%mod; } int find(int x){ return a[x].fax?x:a[x].fa=find(a[x].fa); } void merge(int x,int y,int z){ x=find(x),y=find(y); if(xy)return; key.erase(lower_bound(key.begin(),key.end(),y)); a[x].ins+=a[y].ins+z-1,a[x].out+=a[y].out-2,a[y].fa=x; } struct path{ int x,y,z; path(int u,int v,int w){x=u,y=v,z=w;} friend bool operator <(const path &x,const path &y){ return x.z<y.z; } }; vector<path>paths; void getpath(int x,int fa,int len,int from){ if(g[x].size()!=2){ if(from)paths.push_back(path(from,x,len)); len=1,from=x; } for(auto y:g[x])if(y!=fa)getpath(y,x,len+1,from); } int main(){ scanf("%d",&n); for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),g[x].push_back(y),g[y].push_back(x); init(); getpath(key.front(),0,0,0); sort(paths.begin(),paths.end()); for(int i=n-1,j=0;i;i--){ while(j<paths.size()&&i<n-paths[j].z)merge(paths[j].x,paths[j].y,paths[j].z),j++; res[i]=fac[i]; for(auto x:key)res[i]=1ll*res[i]inv[i-(n-a[x].ins-1)+a[x].out(n-i-1)]%mod; } res[n]=fac[n]; for(int i=1;i<=n;i++)printf("%d\n",res[i]); return 0; }