题解：P13020 [GESP202506 八级] 遍历计数

· · 题解

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

题目链接

转至专栏阅读

解题思路

题目让我们计算一棵树上所有不同的 DFS 序的数量。将题目转化一下：计算在 DFS 的过程中，每一步有多少种选择，然后将所有选择数相乘。

设 V = \{1, 2, \dots, n\} 为树的节点集合，\text{Count}(s) 为从节点 s 出发的不同 DFS 序的数量。总数 \text{Total} 为：\sum_{s \in V} \text{Count}(s)。

先考虑固定起点的情况。对于起点 s，可以按任意顺序访问相邻节点，也就是有 \text{deg}(s)! 种情况，剩下的点也可以按任意顺序访问相邻节点，但是不能访问父节点，所以有 (\text{deg}(u)-1)! 种情况。

以该节点为起点的情况数为：

\begin{align*} \text{Count}(s) &= \text{deg}(s)! \times \prod_{u\in V, u \neq s} (\text{deg}(u) - 1)!\\ &= \text{deg}(s) \times \prod_{u\in V} (\text{deg}(u) - 1)!\\ \end{align*}\\

所以总数为：

\begin{align*} \text{Total} &= \sum_{s \in V} \text{Count}(s) \\ &= \sum_{s\in V} (\text{deg}(s) \times \prod_{u\in V} (\text{deg}(u) - 1)!)\\ &=\prod_{u\in V} (\text{deg}(u) - 1)!\times\sum_{s\in V} \text{deg}(s) \end{align*}

因为所有顶点的度数之和等于边数的两倍。所以在一棵有 n 个节点的树中：

\sum_{s \in V} \text{deg}(s) = 2(n-1)

将此结果代回到原式中，总数为：

\text{Total} = \prod_{u\in V} (\text{deg}(u) - 1)! \times 2(n-1)

注意：当 n=1 时，DFS 序数量为 1，需要特判。

参考代码

#include<iostream>
using namespace std;
const int N=1e5+5,mod=1e9;
int n,ans;
int deg[N],fac[N]={1};
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    ans=2*(n-1);
    if(n==1){
        cout<<1;
        return 0;
    }
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    for(int i=1,x,y;i<n;i++){
        cin>>x>>y;
        deg[x]++,deg[y]++;
    }
    for(int i=1;i<=n;i++) ans=1ll*ans*fac[deg[i]-1]%mod;
    cout<<ans;
    return 0;
}

AC 记录