徐老师的机房维修
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
徐老师的学校最近有电脑被注入了挖矿病毒，为了防止病毒互相传播，徐老师决定尽可能的断开局域网之间的连接学校的网络采用的是树形拓扑结构，共有 $n$ 台设备，其中一部分是路由器，可以上网，一部分是普通设备，需要直接或间接连到路由器上才可以上网
现在徐老师决定尽可能的断开设备之间的连接，但是又要保证所有设备能够上网，也就是当断开一部分连接后，必须保证每个设备依旧能够间接或者直接的连接到路由器
这里很容易发现，因为是树形拓扑结构，每断开一条连接就会导致网络结构变成两块，断开两条连接就会到之后网络结构变成三块，那么如果学校一共有 $k$ 台服务器，徐老师最多能断开 $k - 1$ 条连接
现在徐老师想知道，共有多少种断开连接的方案？这里我们认为两种方案中只要有一条连接不同，这就是两组不同的方案
输入格式
输入第一行包含一个整数 $n$ 表示设备数量第二行包含 $n$ 个整数 $f_i$，表示 $i$ 和 $f_i$ 之间有一条连接
第三行包含 $n$ 个整数 $p_i$，$p_i=0$ 时表示第 $i$ 个节点是普通设备，$p_i=1$ 时表示第 $i$ 个设备是路由器
| 测试点编号 | 数据范围 | 特殊约束 |
| :---: | :---: | :---: |
| $1$ | $2 \leq n \leq 10$ |无 |
| $2 \sim 3$ | $2 \leq n \leq 10^5$ | 保证只有 $2$ 个路由器 |
| $4 \sim 5$ | $2 \leq n \leq 10^5$ | 保证有 $n-1$ 个路由器 |
| $6 \sim 10$ | $2 \leq n \leq 10^5$ |无|
对于所有的数据，均满足 $1 \leq n \leq 10^{5}, 0 \leq f_i < i, p_i$ 一定是 $0$ 或者 $1$
| :---: | :---: | :---: |
| $1$ | $2 \leq n \leq 10$ |无 |
| $2 \sim 3$ | $2 \leq n \leq 10^5$ | 保证只有 $2$ 个路由器 |
| $4 \sim 5$ | $2 \leq n \leq 10^5$ | 保证有 $n-1$ 个路由器 |
| $6 \sim 10$ | $2 \leq n \leq 10^5$ |无|
对于所有的数据，均满足 $1 \leq n \leq 10^{5}, 0 \leq f_i < i, p_i$ 一定是 $0$ 或者 $1$
输出格式
输出徐老师断开连接的方案数，因为数字可能过大，请你将答案对 $1e9+7$ 取模样例
10
0 1 2 1 4 4 4 0 8
0 0 0 1 0 1 1 0 0 12723CSP-S秋季提高组模拟赛(6)
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-10-2 17:15
- 结束于
- 2023-10-12 17:15
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 23
