题目链接：
http://codeforces.com/problemset/problem/461/B
题意：
给定$n$个结点的一棵树，给定每个节点为白色或者黑色，问有多少种删边的方案使得剩下的连通块中只有一个黑点。
数据范围：$2 \le n \le 10^5$
分析：
方案数相关，考虑状态$dp[i][0]:结点i所在连通块中含有一个黑点的方案数，dp[i][0]则表示所在连通块中没有黑点的方案数$
现在我们考虑加上以子节点$u$为根的子树，根据子树是否有黑点分情况考虑是否删掉$i与u$相连的边，将两个连通块的方案数相乘更新$dp[i][0]和dp[i][1]$即可。
代码：
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
| > File Name: 461B.cpp > Author: jiangyuzhu > Mail: 834138558@qq.com > Created Time: 2016/10/11 20:16:05 ************************************************************************/ #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<set> #include<map> #include<algorithm> using namespace std; const int maxn = 1e5 + 5, mod = 1e9 + 7; typedef long long ll; vector<int>G[maxn]; int a[maxn]; ll dp[maxn][2]; void dfs(int now, int pa) { dp[now][a[now]] = 1; for(int i = 0; i < G[now].size(); ++i){ int v = G[now][i]; if(v == pa) continue; dfs(v, now); dp[now][1] = (dp[now][1] * dp[v][1] + dp[now][1] * dp[v][0] + dp[now][0] * dp[v][1]) % mod; dp[now][0] = dp[now][0] * (dp[v][1] + dp[v][0]) % mod; } } int main (void) { int n;scanf("%d", &n); int x; for(int i = 1; i < n; ++i){ scanf("%d", &x); G[x].push_back(i); G[i].push_back(x); } for(int i = 0; i < n; ++i) scanf("%d", &a[i]); dfs(1, -1); printf("%d\n", dp[1][1]); return 0; }
|
