题解详细

Tips:本题解由豆包AI辅助生成，请酌情选择
问题分析与解题思路

1. 核心概念
   等价类：本质是计算不同的 "本质不同" 的放置方式，这些方式无法通过奶牛移动互相转化。
   树的结构分解：树中度数≠2 的节点是 "关键点"（分支点 / 叶子），度数 = 2 的节点是 "链节点"。链节点不影响等价性（奶牛可在链上自由移动），只有关键点的放置才决定等价类。
2. 解题步骤
   步骤 1：预处理阶乘与逆元
   计算阶乘ans[i] = i! mod P（豆包tips：初始 ans 数组存储阶乘）
   计算阶乘的逆元ifac[i] = (i!)^{-1} mod P（豆包tips：运用费马小定理：逆元 = pow (i!, P-2, P)）
   步骤 2：树的结构分解
   找出所有度数≠2 的节点作为 "根节点"（豆包tips：存入 set<root>）
   对每个根节点，DFS 遍历其所在的链，记录根节点到其他根节点的链长度（边数）
   将所有连接两个根节点的链按长度从大到小排序
   步骤 3：并查集合并与计数
   按链长度从小到大处理，用并查集合并根节点 （豆包的tips：反向遍历）
   对于每个 K，计算等价类数量：等价类数 = (总排列数) / (等价变换数)，模意义下用逆元实现除法

代码详解

#include <bits/stdc++.h>
using namespace std;
const int N=100007,P=1000000007;

int n,fa[N],size[N],num[N],ifac[N],ans[N];
vector<int>e[N];
set<int>root;

struct edge{
    int u,v,w;
};vector<edge>vec;
int read(){
    int x=0,c=getchar();
    while(isspace(c)) c=getchar();
    while(isdigit(c)) (x*=10)+=c&15,c=getchar();
    return x;
}

void inc(int&a,int b){
    a+=b-P,a+=a>>31&P;
}

int mul(int a,int b){
    return 1ll*a*b%P;
}

int pow(int a,int b){
    int r=1;
    for(;b;b>>=1,a=mul(a,a)){
        if(b&1)r=mul(a,r);
    }
    return r;
}

int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}

void dfs(int u,int fa,int dep,int root){
    for(int v:e[u]){
        if(v^fa){
            if(e[v].size()==2){
                dfs(v,u,dep+1,root);
            } else if(root<v) {
                vec.push_back({root,v,dep+1});
            }
        }
    }
}

int main(){
    int n=read();
    for(int i=ans[0]=ifac[0]=1;i<=n;++i){
        ifac[i]=pow(ans[i]=mul(ans[i-1],i),P-2);
    }
    for(int i=1,u,v;i<n;++i){
        u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
    }
    for(int u=1;u<=n;++u){
        if(e[u].size()^2){
            num[fa[u]=u]=e[u].size(),dfs(u,0,1,u),size[u]=1,root.insert(u);
        }
    }
    sort(vec.begin(),vec.end(),[](edge a,edge b){return a.w>b.w;});
    for(int i=n-1;i;--i){
        for(int u,v;vec.size()&&vec.back().w+i<n;vec.pop_back()){
	    	u=find(vec.back().u),v=find(vec.back().v),size[u]+=size[v]+vec.back().w-2,num[u]+=num[v]-2,root.erase(v),fa[v]=u;
        }
        for(int x:root){
            ans[i]=mul(ans[i],ifac[i-n+size[x]+(n-i-1)*num[x]]);
        }
    }
    for(int i=1;i<=n;++i){
        cout<<ans[i]<<endl;
    }
    return 0;
}