G8014 [GESP202506 八级] 遍历计数 题解

知识点：树、组合数学、度数统计。

解题思路

设各点度数为d。固定根r的DFS先序由每点孩子的访问排列决定，数量为d[r]!∏其他点(d[v]-1)!。对全部根求和化简为2(n-1)∏(d[v]-1)!。

为什么正确

固定根后，每次对子树的完整访问顺序由孩子排列唯一确定；不同根的先序首项不同，无重复，度数和为2(n-1)给出化简。

易错点

单节点无边时答案为1；模数为10^9，不是素数，但这里只做乘法，不需模逆元。

复杂度

时间O(n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>d(n+1);
    for(int i=1;i<n;i++) {
        int u,v;
        cin>>u>>v;
        d[u]++;
        d[v]++;
    }
    if(n==1) {
        cout<<1;
        return 0;
    }
    vector<long long>f(n+1,1);
    for(int i=1;i<=n;i++)f[i]=f[i-1]*i%1000000000;
    long long ans=2LL*(n-1);
    for(int i=1;i<=n;i++)ans=ans*f[d[i]-1]%1000000000;
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用14个自行生成的测试点。