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

此题解思路为树形DP

题意

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

思路

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

设置

f_i

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

设置一个存储边的 vector:e

不难发现:

$f_i = \prod_{e_i.size}^{i=0}f_{e_{i,j}} \times A_{e_i.size}^{e_i.size}$

再推一下，也就是：

$f_i = \prod_{e_i.size}^{i=0}f_{e_{i,j}} \times (e_i.size)!$

这样，

O(n^2)

的代码就出现了。

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

推荐看一眼

CPP

#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为根节点时，父亲节点的那一块就是

$\frac{f_{fath}}{f_{now} \times e_{fath}.size}$

然后，除了父亲节点那一块，其他节点也在之前处理过了，就是

f_{now}

,根据我们之前推出来的公式：

f_i = \prod_{e_i.size}^{i=0}f_{e_{i,j}} \times (e_i.size)!

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

$\frac{f_{fath}}{f_{now} \times e_{fath}.size} \times f_{now} \times e_{now}.size$

约分后得出最终公式：

$\frac{f_{fath} \times e_{now}.size}{e_{fath}.size}$

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

我们可以提前计算一下

\frac{f_{fath}}{e_{fath}.size}

将这个东西叫做

lstf

然后经过计算可以得出

lstf_{now} = lstf_{fath}

最后这个算式就是

f[son] = 1ll \times lstf_{now} \times e_{son}.size

(我这里是从now传递给son)

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

CPP

#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 就是不让你复制;
}

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

文章操作

此题解思路为树形DP

题意

思路

相关推荐

评论

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