将奶牛的状态用序列${a_{1},a_{2},...,a_{m}}$来描述，其中$a_{i}$表示第$i$头奶牛的位置（奶牛数量为$m$）
下面，先来考虑对于某个特定的$m$如何处理：
对于一条简单路径，如果路径中（不包括端点）所有点度数均为2且端点的度数均不为2（允许为1），则称该路径为一条"链"，显然树上每一条边都恰属于一条链
对于一条链，假设链上的点（包括端点）构成的集合为$C$，删去$C$中的点后被划分为$A$和$B$两个连通块
记$k=|C|-(n-m)$，若存在$kge 0$的链，那么任取一个状态${a_{i}}$并令$S={a_{i}}$（集合），简单分析不难得到若$A,B otsubseteq S$则$Scap C e empty$，因此构造如下变换：
若$A otsubseteq S$，将$Scap C$中最靠近$A$中（任意一点）的点（显然唯一）移动到$A$中（不关心顺序），同理对$B$做此操作，那么即有$A,Bsubseteq S$，进而由此可得$|Scap C|=k$
根据此变换，每一个状态都与某个$A,Bsubseteq S$的状态等价，因此仅考虑这类状态中的等价类数即可
注意到$Scap C$中的点恒在$C$中且顺序不变，因此这些点的贡献可以看作$k!{mchoose k}$，同时由于这些点使得$A$和$B$中点无法交换，因此又即可以变为两个子问题
具体的，令$C_{A}$和$C_{B}$分别为最靠近$A$和$B$中的$|C|-k$个点，子问题的点集即分别为$Acup C_{A}$和$Bcup C_{B}$，并且分别要选$|A|$和$|B|$头奶牛，另外编号选择还有${m-kchoose |A|}$的贡献
关于$C_{A}$和$C_{B}$，即将中间的$k$个点都移到另一边，那么就空出了这$|C|-k$个位置
重复此过程，直至不存在$kge 0$的链，那么这个子问题中任意两个状态都等价，这可以归纳证明
下面，来简单分析一下此递归过程：
1.递归过程中$n-m$的值不变，且代入可得$|C_{A}|=|C_{B}|=n-m$
2.若$mle n-2$，也即$|C_{A}|=|C_{B}|ge 2$，那么注意到链的端点仍存在且度数不变，而除了$C_{A}$和$C_{B}$的末尾外其余点度数也不会变化，从而链的划分形式变化即删除了一条链$C$并加入了$C_{A}$和$C_{B}$这两条链
因此，链只需要初始预处理并找出所有$|C|ge n-m$的链，假设链长（指$|C|$）依次为$l_{1},l_{2},...,l_{k}$，并且将这些链中的点删除后（保留端点），连通块节点数依次为$a_{1},a_{2},...,a_{k+1}$（显然删除一条链恰好增加一个连通块），那么贡献即
$$
{mchoose a_{i}-(n-m),l_{i}-(n-m)}prod_{i=1}^{k}(l_{i}-(n-m))!
$$
注意$a_{i}$要包含$C_{A}$和$C_{B}$，计算方式即$(n-m-1)cdot$参与删除的次数+当前节点数
同时，此时剩下的每一个连通块中不存在$kge 0$的链，根据前面的结论任意两个状态等价，也即对答案的贡献为1，因此上述贡献即为答案
对于所有$1le mle n-2$，不难发现$sum k$中每一条链贡献恰为$o(l_{i})$，而由于一条边恰属于一条链因此该值和为$o(n)$，换言之可以暴力计算（指$o(k)$）上述贡献
由此，先将所有链删除，并将其按照$m$从大到小后依次合并，使用并查集维护即可
另外，为了快速找到所有$a_{i}$，可以用一个set维护并查集的根
最终，还有$mge n-1$的情况，显然此时答案即为$m!$
时间复杂度为$o(nlog n)$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 100005 4 #define mod 1000000007 5 #define ll long long 6 struct Data{ 7 int x,y,len; 8 bool operator < (const Data &k)const{ 9 return len<k.len; 10 } 11 }; 12 vector<int>v[N]; 13 vector<Data>L; 14 set<int>S; 15 set<int>::iterator it; 16 int n,rt,x,y,fac[N],inv[N],d[N],f[N],sz[N],Sz[N],ans[N]; 17 int find(int k){ 18 if (k==f[k])return k; 19 return f[k]=find(f[k]); 20 } 21 int merge(int x,int y){ 22 x=find(x),y=find(y); 23 S.erase(y); 24 f[y]=x,sz[x]+=sz[y],Sz[x]+=Sz[y]; 25 return x; 26 } 27 int C(int n,int m){ 28 return (ll)fac[n]*inv[m]%mod*inv[n-m]%mod; 29 } 30 void dfs(int k,int fa){ 31 f[k]=fa; 32 if ((fa)&&(d[k]!=2)){ 33 int pos=f[k],tot=2; 34 for(;d[pos]==2;pos=f[pos])tot++; 35 L.push_back(Data{k,pos,tot}); 36 } 37 for(int i=0;i<v[k].size();i++) 38 if (v[k][i]!=fa)dfs(v[k][i],k); 39 } 40 int main(){ 41 fac[0]=inv[0]=inv[1]=1; 42 for(int i=1;i<N;i++)fac[i]=(ll)fac[i-1]*i%mod; 43 for(int i=2;i<N;i++)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod; 44 for(int i=1;i<N;i++)inv[i]=(ll)inv[i-1]*inv[i]%mod; 45 scanf("%d",&n); 46 for(int i=1;i<n;i++){ 47 scanf("%d%d",&x,&y); 48 d[x]++,d[y]++; 49 v[x].push_back(y); 50 v[y].push_back(x); 51 } 52 for(int i=1;i<=n;i++) 53 if (d[i]!=2)rt=i; 54 dfs(rt,0); 55 sort(L.begin(),L.end()); 56 for(int i=1;i<=n;i++){ 57 f[i]=i,sz[i]=1,Sz[i]=d[i]; 58 if (d[i]!=2)S.insert(i); 59 } 60 for(int i=n-2,j=0;i;i--){ 61 while ((j<L.size())&&(L[j].len<n-i)){ 62 int k=merge(L[j].x,L[j].y); 63 sz[k]+=L[j].len-2,Sz[k]-=2; 64 j++; 65 } 66 ans[i]=1; 67 int m=i; 68 for(it=S.begin();it!=S.end();it++){ 69 int s=sz[(*it)]+(n-i-1)*Sz[(*it)]-(n-i); 70 ans[i]=(ll)ans[i]*C(m,s)%mod; 71 m-=s; 72 } 73 for(int k=j;k<L.size();k++){ 74 int l=L[k].len-(n-i); 75 ans[i]=(ll)ans[i]*C(m,l)%mod*fac[l]%mod; 76 m-=l; 77 } 78 } 79 ans[n-1]=fac[n-1],ans[n]=fac[n]; 80 for(int i=1;i<=n;i++)printf("%d ",ans[i]); 81 return 0; 82 }