刷题记录:牛客NC19782Tree

传送门:牛客

题目描述:

修修去年种下了一棵树，现在它已经有n个结点了。
修修非常擅长数数，他很快就数出了包含每个点的连通点集的数量。
澜澜也想知道答案，但他不会数数，于是他把问题交给了你。
输入:
6
1 2
1 3
2 4
4 5
4 6
输出:
12
15
7
16
9
9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这道题很好的帮我巩固了换根dp+乘法逆元+快速幂的知识,自我感觉是一道很好的题目

主要思路:

1. 首先我们肯定能想到树形dp,并且易想到使用$d[u]数组来记录以u为根的子树的联通点集的数量$,那么此时我们只要考虑转移方程就行了.
2. 对于我们的转移方程,我们观察一下,就会发现因为是联通点集的原因,所以对于我们的根节点u来说,我们的u是一定需要的.但是我们的u的儿子节点却可以不用.所以当我们选择一个儿子节点的联通点集时,我们分儿子节点选取或者不选取.当我们的儿子节点选取时,我们的儿子节点的所有联通点集都与我们的u节点是联通的,也就是若我们的儿子节点联通那么此时我们的贡献就是所有儿子节点的联通点集相乘.假设我们的儿子节点有一个不选取时,那么对于这种情况,我们也会贡献出一个可能性.所以对于我们的所有情况,就是所有的 $\prod (儿子节点的联通点集+1)$
3. 但是因为我们的题目求的是每一个节点的所有儿子的联通点集,但是由于我们在上述方法中求出的联通点集是假定了父亲的,所以我们的答案并不是我们最终的答案.所以我们此时需要使用换根的方法来求出父亲节点那一部分的贡献.那么对于我们的父亲节点,假设我们此时使用$dp[u]$记录下来了我们的联通点集,那么对于我们此时的儿子节点来说,我们如果使用我们的$dp[u]/(d[v]+1)$,也就是除去我们的此时的儿子的贡献,是不是就是我们的另一边的贡献$d[u]$了??.那么此时我们的最终答案就是$d[v]\ast (d[u]+1)$即可

但是,由于我们的最终答案是需要取模的,并且我们在运算过程中用到了除法,那么对于我们的除法来说,是不满足我们的取余公式的,也就是

在下列中 mod=1e9+7

$(a/b)\%mod\ne (a\%mod)/(b\%mod)$

所以此时我们得想另一个办法来解决除法取模的问题

对于乘法逆元,有一个比较简单的计算方法,使用到了快速幂和费马小定理

对于费马小定理.我们有$a^{p-1}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}p$ 需要我们的$a\ne p,p为质数$

然后对于我们的$a/b\%mod$,我们可以找到一个X满足$bx\equiv 1\%mod$

那么此时我们显然有$a/b\ast b\ast x\equiv a/b(\%mod)$,然后我们就有$a\ast x\equiv a/b(\%mod)$

然后我们只要找出我们的b的逆元X即可.然后我们使用费马小定理,

有$b^{p-2}\ast b\equiv 1\%mod)$,然后我们巧妙的就发现我们的$b^{p-2}$恰好就是我们的乘法逆元,所

以我们直接使用快速幂求解即可

但是对于这道题,由于我们的模数比较小,可能存在我们的(d[v]+1)%mod=0的情况,对于这种情况我们就无法使用逆元了.所以此时我们准备暴力的去求解另一边的贡献.

对于这个暴力我们的算法也很简单,就是在之前求解d数组的算法中,加入一个限制不能遍历我们此时的子树v即可

下面是我们的代码部分:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000010
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int n;
vector<ll>tree[maxn];
ll d[maxn];ll dp[maxn];
const int mod=1e9+7;
ll qpow(ll a,ll b) {
	ll ans=1;
	while(b) {
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
void dfs1(ll u,ll pre_u) {
	d[u]=1;
	for(int i=0;i<tree[u].size();i++) {
		ll v=tree[u][i];
		if(v==pre_u) continue;
		dfs1(v,u);
		d[u]=d[u]*(d[v]+1)%mod;
	}
	return ;
}
void dfs2(ll u,ll pre_u) {
	for(int i=0;i<tree[u].size();i++) {
		int v=tree[u][i];
		if(v==pre_u) continue;
		ll inv=qpow(d[v]+1,mod-2);
		if(inv) {
			dp[v]=(inv*dp[u]%mod+1)%mod*d[v]%mod;
		}else {
			ll ans=1;
			for(int j=0;j<tree[u].size();j++) {
				int vv=tree[u][j];
				if(vv==v||vv==pre_u) continue;
				ans=ans*(d[vv]+1)%mod;
			}
			dp[v]=(d[v]*(ans+1))%mod;
		}
		dfs2(v,u);
	}
	return ;
}
int main() {
	n=read();int u,v;
	for(int i=1;i<=n-1;i++) {
		u=read();v=read();
		tree[u].push_back(v);
		tree[v].push_back(u);
	}
	dfs1(1,0);
	dp[1]=d[1];
	dfs2(1,0);
	for(int i=1;i<=n;i++) printf("%lld\n",dp[i]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82