1.0 秒
131,072.0 KB
80 分
5 级题
苹果曼有一棵 n 个点的树. 有一些 (至少一个) 结点被标记为黑色, 有一些结点被标记为白色.
现在考虑一个包含 k(0 ≤ k <n) 条树边的集合. 如果苹果曼删除这些边, 那么会将这个树分成 (k+1) 个部分. 每个部分还是一棵树.
现在苹果曼想知道有多少种边的集合, 可以使得删除之后每一个部分恰好包含一个黑色结点. 答案对 1000000007 取余即可.
收起
输入
单组测试数据.
- 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-3193995.html