专栏文章

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

GGeorge__Pig
P13020题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip0hdb8
此快照首次捕获于
2025/12/03 04:09
3 个月前
此快照最后确认于
2025/12/03 04:09
3 个月前
查看原文

零

虽然本人思路看上去较冗长，但展现的是本人在考场上的一步步简化问题的步骤，希望能给读者带来帮助。

一

首先，考虑以1为起点遍历的情况。考虑树形dp。
令fuf_u以 uu 为顶点的子树的不同方案数
设 uu 的儿子为 v1,v2,...,vkv_1,v_2,...,v_k ，则有
fu=Akk×∏i=1k fvif_u=A_k^k \times \prod_{i = 1}^{k} \ f_{v_i}
其中 AkkA_k^k 表示 kk 的全排列数量
细节看代码（AA 数组预处理即可）：
CPP
#define int long long
m=1e9
void dfs(int pos,int fa){
	f[pos]=1;
	for(auto son:e[pos])
		if(son!=fa){
			dfs(son,pos);
			cnt[pos]++;
			f[pos]=f[pos]*f[son]%m;
		}
	f[pos]=f[pos]*A[cnt[pos]]%m;
}

二

上面的 dfsdfs 时间复杂度为 O(n)O(n) ，nn 个顶点肯定过不了100%
注意到：
当点 u,vu,v 之间有边相连时，分别以 u,vu,v 为根遍历，得到的 ff 数组只有 fu,fvf_u,f_v 发生改变。希望找到二者的关系
考虑任意一边 (u,v)(u,v)，设两点度数为 du,dvd_u,d_v
以 uu 为节点时
fu=Adudu×(∏i=1du−1 fui)×fv=Adudu×(∏i=1du−1 fui)×Adv−1dv−1×(∏i=1dv−1 fvi)f_u=A_{d_u}^{d_u} \times (\prod_{i = 1}^{d_u-1} \ f_{u_i}) \times f_v=A_{d_u}^{d_u} \times (\prod_{i = 1}^{d_u-1} \ f_{u_i}) \times A_{d_v-1}^{d_v-1} \times (\prod_{i = 1}^{d_v-1} \ f_{v_i})
以 vv 为节点时
fv′=Advdv×(∏i=1dv−1 fvi)×fu′=Advdv×(∏i=1dv−1 fvi)×Adu−1du−1×(∏i=1du−1 fui)f_v'=A_{d_v}^{d_v} \times (\prod_{i = 1}^{d_v-1} \ f_{v_i}) \times f_u'=A_{d_v}^{d_v} \times (\prod_{i = 1}^{d_v-1} \ f_{v_i}) \times A_{d_u-1}^{d_u-1} \times (\prod_{i = 1}^{d_u-1} \ f_{u_i})
二者相比得：
ansuansv=fufv′=Adv−1dv−1×AduduAdvdv×Adu−1du−1=dudv\frac{ans_u}{ans_v}=\frac{f_u}{f_v'}=\frac{A_{d_v-1}^{d_v-1} \times A_{d_u}^{d_u}}{A_{d_v}^{d_v} \times A_{d_u-1}^{d_u-1}}=\frac{d_u}{d_v}
所以，可以用深搜再跑一遍，计算出每个ansans
但是 模运算不支持除法

三

由上文知
ansuansv=dudv\frac{ans_u}{ans_v}=\frac{d_u}{d_v}
即 ansv=fudu×dvans_v=\frac{f_u}{d_u} \times d_v
而 fudu\frac{f_u}{d_u} 与 vv 无关 令 λ=fuduλ=\frac{f_u}{d_u} 则 ansv=λdvans_v=λd_v
所求为
sum=∑i=1n ansi=λ∑i=1n disum=\sum_{i = 1}^{n} \ ans_i=λ\sum_{i = 1}^{n} \ d_i
注意到 ∑i=1n di=2(n−1)\sum_{i = 1}^{n} \ d_i=2(n-1) 故所求为
2λ(n−1)2λ(n-1)
树形dpdp跑出 λ=fuduλ=\frac{f_u}{d_u} 即可
代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
vector<int>e[N];
int n,u,v,A[N],f[N],cnt[N],m=1e9;
void dfs(int pos,int fa){
	f[pos]=1;
	for(auto son:e[pos])
		if(son!=fa){
			dfs(son,pos);
			cnt[pos]++;
			f[pos]=f[pos]*f[son]%m;
		}
	if(pos!=1) f[pos]=f[pos]*A[cnt[pos]]%m;//f[1]即为上文的λ
	else f[pos]=f[pos]*A[cnt[pos]-1]%m;
}
signed main(){
	cin>>n;
	if(n==1){cout<<1;return 0;} //n=1时没有边，一切免谈
	A[0]=1;
	for(int i=1;i<=1e5;i++) A[i]=A[i-1]*i%m;
	for(int i=1;i<n;i++){
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1,0);
	cout<<f[1]*(n-1)*2%m;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...