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

· · 题解

我居然是第一个写题解的！！！

此题解思路为树形DP

题意

给定一棵，求出它有多少个dfs序（这个dfs序根节点和下一个遍历的节点都不一定）

思路

这里给大家一个巧妙的思路

设置 f_i为以1为根节点，i以及它的后辈构成的这棵树dfs序的数量

设置一个存储边的 vector:e

不难发现:

再推一下，也就是：

这样， O(n^2)的代码就出现了。

退出了这个公式的我立马就变写出了下面的代码

推荐看一眼

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9;
int n,f[100005],lstf[100005],fact[100005];
long long ans;
vector<int> e[100005];
void dfs(int now,int fath,int root){
    f[now] = 1;
    int sz = e[now].size();
    for (int i = 0;i < sz;i++){
        int son = e[now][i];
        if (son == fath) continue;
        dfs(son,now,root);
        f[now] = 1ll * f[now] * f[son] % mod;
    }
    if (now == root) f[now] = 1ll * f[now] * fact[sz] % mod;
    else if (sz > 1) f[now] = 1ll * f[now] * fact[sz-1] % mod;//注意，这里sz-1是因为还有父亲节点，根节点没有父亲，所以不用减
}

int main(){
    scanf("%d",&n);
    fact[1] = fact[0] = 1;
    for (int i = 2;i <= 100000;i++) fact[i] = 1ll * fact[i-1] * i % mod;//预制
    for (int i = 1;i < n;i++){
        int u,v;scanf("%d%d",&u,&v);
        e[u].push_back(v);e[v].push_back(u);
    }
    for (int i = 1;i <= n;i++){
        dfs(i,-1,i);
        ans = (ans + (long long)f[i]) % mod;
    }
    cout << ans;
}

风风火火的交上去后，直接T飞~~

为什么呢？

一看到n \geq 1e5直接释怀了

那怎么办呢？

在考场上的我写满了三页草稿纸，终于想出来一种O(2n)的做法

因为是动态规划，所以当前now节点的父亲节点fath一定知道它的实际答案

而且，节点now作为根节点时，少算的只有它的父亲节点，那对于now为根节点时，父亲节点的那一块就是

然后，除了父亲节点那一块，其他节点也在之前处理过了，就是f_{now},根据我们之前推出来的公式：f_i = \prod_{e_i.size}^{i=0}f_{e_{i,j}} \times (e_i.size)!

就可以推出以now为根节点的公式

约分后得出最终公式：

那我们怎么计算出这个算式呢？

我们可以提前计算一下\frac{f_{fath}}{e_{fath}.size}

将这个东西叫做lstf

然后经过计算可以得出lstf_{now} = lstf_{fath}

最后这个算式就是f[son] = 1ll \times lstf_{now} \times e_{son}.size(我这里是从now传递给son)

最后就是喜闻乐见的代码环节了

#include<bits/stdc++.h>
using namespace std;

const int mod = 1e9;
int n,f[100005],lstf[100005],fact[100005];
vector<int> e[100005];
long long ans;
void dfs(int now,int fath,int root){
    f[now] = 1;
    int sz = e[now].size();
    for (int i = 0;i < sz;i++){
        int son = e[now][i];
        if (son == fath) continue;
        dfs(son,now,root);
        f[now] = 1ll * f[now] * f[son] % mod;
    }
    if (now == root){
        lstf[now] = 1ll * f[now] * fact[sz-1] % mod;
        f[now] = 1ll * f[now] * fact[sz] % mod;
    //这里顺序颠倒就会先计算f,然后会乘上两遍fact[sz-1]
    }
    else lstf[now] = f[now] = 1ll * f[now] * fact[sz-1] % mod;//因为lstf本来就是计算fact[sz] / sz,所以非一号节点的节点lstf=f
}
void dfs1(int now,int fath){
    int sz = e[now].size();
    //ans = (ans + (long long)f[now]) % mod;
  //我偷偷把计算ans的代码给删了，不许复制
    for (int i = 0;i < sz;i++){
        int son = e[now][i];
        if (son == fath) continue;
        f[son] = 1ll * lstf[now] * e[son].size() % mod;
        lstf[son] = lstf[now];
        dfs1(son,now);
    }
}//这个就是用来计算答案

int main(){
    scanf("%d",&n);
    fact[0] = fact[1] = 1;
    for (int i = 1;i <= 100000;i++) fact[i] = 1ll * fact[i-1] * i % mod;//预制
    for (int i = 1;i < n;i++){
        int u,v;scanf("%d%d",&u,&v);
        e[u].push_back(v);e[v].push_back(u);
    }
    dfs(1,-1,1);
    dfs1(1,-1);
    printf("%d",ans);
    return 就是不让你复制;
}