传送门：https://ac.nowcoder.com/acm/contest/203/B
题意
给一棵树，对于每个节点，输出与它相连的所有子集个数。
思路
树，节点，计数-树形dp。
设f[i]为以i为根节点的字树中，包括i的子集个数，所以对于根节点，答案为f[root]。
状态转移方程：
$$f[u]=\prod(f[v]+1)\;\;v为与u相连儿子$$
为什么+1，因为自己是子集的一部分。
上面说到，只有对于根节点，ans才为f[root]，但是不是根节点呢？
最简单的方法是，把每个点当作root，dfs一遍。但是数据范围不允许。
$但是我们看到对于以u为根节点的叶子节点，只有父亲节点那边的子集个数没有统计。
所以我们再dfs’一遍，首先是没有父亲，所以ans=f[u]，然后利用父亲更新节点。
如果更新呢？
f[u]已经统计了所有子节点，没有统计父亲节点，所以需要乘上父亲节点那边的贡献。
贡献为$\frac{ans[fa]}{f[u]+1}$，所以$ans[u]=(\frac{ans[fa]}{f[u]+1}+1)*f[u]$
对于$(f[u]+1) \% mod=0$，因为0没有逆元，所以要特别统计（最大坑点）。 最简单的就是以它为根节点dfs一遍，ans=f[u]。
Code
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
| ##include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int N = 1e6 + 10;
ll quick_pow(ll a, ll b) {
ll ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans % mod;
}
vector<int> g[N];
ll ans[N], f[N];
void dfs1(int u, int fa) {
f[u] = 1;
for(auto v : g[u]) {
if(v == fa) continue;
dfs1(v, u);
f[u] = f[u] * (f[v] + 1) % mod;
}
}
void dfs2(int u, int fa) {
if(fa != -1) {
if((f[u] + 1) % mod == 0) {
dfs1(u, -1);
ans[u] = f[u];
}
else ans[u] = (ans[fa] * (quick_pow(1 + f[u], mod - 2) % mod) % mod + 1) * f[u] % mod;
}
else ans[u] = f[u];
for(auto v : g[u]) {
if(v == fa) continue;
dfs2(v, u);
}
}
void solve() {
int n; cin >> n;
for(int i = 1;i < n; i++) {
int u, v; cin >> u >> v;
g[u].eb(v);
g[v].eb(u);
}
dfs1(1, -1);
dfs2(1, -1);
for(int i = 1;i <= n; i++) cout << ans[i] << endl;
}
signed main() {
solve();
}
|
本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/03/25/2018-nowcoder-guoqing-day3-b-tree/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！