主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
T1 树の拆分 ACCode
最后更新于 2025-07-31 09:49:46
作者
LiGaYb
分类
个人记录
复制 Markdown
查看原文
删除文章
更新内容
```cpp #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10, mod = 1e9 + 7; int n, p[maxn], x[maxn], h[maxn], e[maxn * 2], ne[maxn * 2], idx; long long dp[maxn][2]; void add(int a, int b){ e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } void dfs(int u, int fa) { dp[u][0] = (x[u] == 0); dp[u][1] = (x[u] == 1); for (int i = h[u]; i != -1; i = ne[i]){ int v = e[i]; if (v == fa) continue; dfs(v, u); long long t0 = dp[u][0], t1 = dp[u][1]; dp[u][0] = (t0 * dp[v][0] + t0 * dp[v][1]) % mod; dp[u][1] = (t1 * dp[v][0] + t0 * dp[v][1] + t1 * dp[v][1]) % mod; } } int main() { memset(h, -1, sizeof h); cin >> n; for (int i = 1; i < n; i++) { cin >> p[i]; add(p[i], i); add(i, p[i]); } for (int i = 0; i < n; i++) { cin >> x[i]; } dfs(0, 1); cout << dp[0][1] << endl; return 0; } ```
正在渲染内容...
点赞
0
收藏
0
