1.0 秒
131,072.0 KB
80 分
5 级题
苹果曼有一棵 n 个点的树. 有一些 (至少一个) 结点被标记为黑色, 有一些结点被标记为白色.
现在考虑一个包含 k(0 ≤ k <n)条树边的集合. 如果苹果曼删除这些边, 那么会将这个树分成 (k+1) 个部分. 每个部分还是一棵树.
现在苹果曼想知道有多少种边的集合, 可以使得删除之后每一个部分恰好包含一个黑色结点. 答案对 1000000007 取余即可.
收起
输入
单组测试数据.
第一行有一个整数 n (2 ≤ n ≤ 10^5), 表示树中结点的数目.
第二行有 n-1 个整数 p[0],p[1],...,p[n-2] (0 ≤ p[i] ≤ i). 表示 p[i]和 (i+1) 之间有一条边. 结点从 0 开始编号.
第三行给出每个结点的颜色, 包含 n 个整数 x[0],x[1],...,x[n-1] (x[i]是 0 或者 1). 如果 x[i]是 1, 那么第 i 个点就是黑色的, 否则是白色的.
输出
输出答案占一行.
输入样例
3 0 0 0 1 1
输出样例
- 2
- #include <bits/stdc++.h>
- #define rg register int
- using namespace std;
- typedef long long ll;
- const ll mod = 1e9 + 7;
- const int maxn = 2e5 + 10;
- struct node {
- int to, nx;
- } o[maxn];
- int n, tot, head[maxn];
- inline void add_edge(int u, int v) {
- o[++tot].to = v;
- o[tot].nx = head[u];
- head[u] = tot;
- }
- int color[maxn];
- ll dp[maxn][6];
- inline void solve(int cur, int f) {
- dp[cur][color[cur]] = 1;
- for (register int i = head[cur]; i; i = o[i].nx) {
- int to = o[i].to;
- if (to == f)continue;
- solve(to, cur);
- dp[cur][1] = ((dp[cur][1] * (dp[to][1] + dp[to][0])) % mod + dp[cur][0] * dp[to][1] % mod) % mod;
- dp[cur][0] = (dp[cur][0] * (dp[to][0] + dp[to][1])) % mod;
- }
- }
- int main() {
- #ifndef ONLINE_JUDGE
- freopen("splay.txt", "r", stdin);
- #endif
- scanf("%d", &n);
- for (register int i = 1; i < n; ++i) {
- int x;
- scanf("%d", &x);
- add_edge(x, i);
- //add_edge(i,x);
- }
- for (register int i = 0; i < n; ++i)scanf("%d", &color[i]);
- solve(0, -1);
- printf("%lld\n", dp[0][1]);
- return 0;
- }
苹果曼和树
来源: http://www.bubuko.com/infodetail-3193996.html