A7678 | Select from Subtrees
时间限制2s
内存限制1024MB
通过 / 提交0/0
题目描述
有一棵包含 $N$ 个顶点的有根树 $T$，顶点编号为顶点 $1$、顶点 $2$、$\ldots$、顶点 $N$。
顶点 $1$ 是树 $T$ 的根，对于每个顶点 $i$（$2 \leq i \leq N$），其（直接）父节点为 $P_i$。
此外，顶点 $i$（$1 \leq i \leq N$）上放置了 $C_i$ 颗糖果。所有 $(C_1 + C_2 + \cdots + C_N)$ 颗糖果彼此互不相同。
高桥向 $N$ 只松鼠下达了指令。具体而言，他向第 $i$ 只松鼠（$1 \leq i \leq N$）下达如下指令：
* 从以顶点 $i$ 为根的子树中选择并收集 $D_i$ 颗糖果。
不同松鼠不能取走同一颗糖果。
请输出满足要求的糖果选取方案总数对 $998244353$ 取模的结果。
注意：即使最终被选中的糖果集合完全相同，只要选取这些糖果的松鼠不同，则视为不同的方案。
若无法让所有松鼠均按指令取回糖果，则输出 $0$。
顶点 $1$ 是树 $T$ 的根，对于每个顶点 $i$（$2 \leq i \leq N$），其（直接）父节点为 $P_i$。
此外，顶点 $i$（$1 \leq i \leq N$）上放置了 $C_i$ 颗糖果。所有 $(C_1 + C_2 + \cdots + C_N)$ 颗糖果彼此互不相同。
高桥向 $N$ 只松鼠下达了指令。具体而言，他向第 $i$ 只松鼠（$1 \leq i \leq N$）下达如下指令：
* 从以顶点 $i$ 为根的子树中选择并收集 $D_i$ 颗糖果。
不同松鼠不能取走同一颗糖果。
请输出满足要求的糖果选取方案总数对 $998244353$ 取模的结果。
注意：即使最终被选中的糖果集合完全相同，只要选取这些糖果的松鼠不同，则视为不同的方案。
若无法让所有松鼠均按指令取回糖果，则输出 $0$。
输入格式
输入从标准输入中按以下格式给出：
> $N$
> $P_2$ $P_3$ $\ldots$ $P_N$
> $C_1$ $C_2$ $\ldots$ $C_N$
> $D_1$ $D_2$ $\ldots$ $D_N$
> $N$
> $P_2$ $P_3$ $\ldots$ $P_N$
> $C_1$ $C_2$ $\ldots$ $C_N$
> $D_1$ $D_2$ $\ldots$ $D_N$
输出格式
输出选择糖果的可能方案数，对 $998244353$ 取模。
输入输出样例
输入 #1
5 1 1 3 3 1 2 1 2 3 1 1 3 1 1
输出 #1
144
输入 #2
2 1 1 1 2 1
输出 #2
0
输入 #3
3 3 1 1000000000 1 1 1 1 1
输出 #3
1755647
**样例 1 解释：**
我们将糖果编号，使得顶点 $1$ 上有糖果 $1$，顶点 $2$ 上有糖果 $2, 3$，顶点 $3$ 上有糖果 $4$，顶点 $4$ 上有糖果 $5, 6$，顶点 $5$ 上有糖果 $7, 8, 9$。
一种可行的选糖方式如下：
* 松鼠 $1$ 从以顶点 $1$ 为根的子树（包含顶点 $1, 2, 3, 4, 5$）中收集糖果 $3$；
* 松鼠 $2$ 从以顶点 $2$ 为根的子树（仅含顶点 $2$）中收集糖果 $2$；
* 松鼠 $3$ 从以顶点 $3$ 为根的子树（包含顶点 $3, 4, 5$）中收集糖果 $4, 7, 9$；
* 松鼠 $4$ 从以顶点 $4$ 为根的子树（仅含顶点 $4$）中收集糖果 $6$；
* 松鼠 $5$ 从以顶点 $5$ 为根的子树（仅含顶点 $5$）中收集糖果 $8$。
注意，以下方式被视为另一种不同的方案：
* 松鼠 $1$ 从以顶点 $1$ 为根的子树（包含顶点 $1, 2, 3, 4, 5$）中收集糖果 $\mathbf{2}$；
* 松鼠 $2$ 从以顶点 $2$ 为根的子树（仅含顶点 $2$）中收集糖果 $\mathbf{3}$；
* 松鼠 $3$ 从以顶点 $3$ 为根的子树（包含顶点 $3, 4, 5$）中收集糖果 $4, 7, 9$；
* 松鼠 $4$ 从以顶点 $4$ 为根的子树（仅含顶点 $4$）中收集糖果 $6$；
* 松鼠 $5$ 从以顶点 $5$ 为根的子树（仅含顶点 $5$）中收集糖果 $8$。
总共有 $144$ 种合法方案，因此输出 $144$ 对 $998244353$ 取模的结果，即 $144$。
**样例 2 解释：**
该树仅在顶点 $1$ 和 $2$ 上共分布两颗糖果，因此无法按题目要求让两只松鼠均成功收集糖果。
故输出 $0$。
**样例 3 解释：**
请注意，需输出方案数对 $998244353$ 取模的结果。
### 约束条件
* $2 \leq N \leq 2 \times 10^5$
* $1 \leq P_i \leq N$
* $1 \leq C_i \leq 10^9$
* $1 \leq D_i$
* $D_1 + D_2 + \cdots + D_N \leq 10^6$
* 所有输入值均为整数。
* $T$ 是一棵以顶点 $1$ 为根的有根树。
我们将糖果编号，使得顶点 $1$ 上有糖果 $1$，顶点 $2$ 上有糖果 $2, 3$，顶点 $3$ 上有糖果 $4$，顶点 $4$ 上有糖果 $5, 6$，顶点 $5$ 上有糖果 $7, 8, 9$。
一种可行的选糖方式如下：
* 松鼠 $1$ 从以顶点 $1$ 为根的子树（包含顶点 $1, 2, 3, 4, 5$）中收集糖果 $3$；
* 松鼠 $2$ 从以顶点 $2$ 为根的子树（仅含顶点 $2$）中收集糖果 $2$；
* 松鼠 $3$ 从以顶点 $3$ 为根的子树（包含顶点 $3, 4, 5$）中收集糖果 $4, 7, 9$；
* 松鼠 $4$ 从以顶点 $4$ 为根的子树（仅含顶点 $4$）中收集糖果 $6$；
* 松鼠 $5$ 从以顶点 $5$ 为根的子树（仅含顶点 $5$）中收集糖果 $8$。
注意，以下方式被视为另一种不同的方案：
* 松鼠 $1$ 从以顶点 $1$ 为根的子树（包含顶点 $1, 2, 3, 4, 5$）中收集糖果 $\mathbf{2}$；
* 松鼠 $2$ 从以顶点 $2$ 为根的子树（仅含顶点 $2$）中收集糖果 $\mathbf{3}$；
* 松鼠 $3$ 从以顶点 $3$ 为根的子树（包含顶点 $3, 4, 5$）中收集糖果 $4, 7, 9$；
* 松鼠 $4$ 从以顶点 $4$ 为根的子树（仅含顶点 $4$）中收集糖果 $6$；
* 松鼠 $5$ 从以顶点 $5$ 为根的子树（仅含顶点 $5$）中收集糖果 $8$。
总共有 $144$ 种合法方案，因此输出 $144$ 对 $998244353$ 取模的结果，即 $144$。
**样例 2 解释：**
该树仅在顶点 $1$ 和 $2$ 上共分布两颗糖果，因此无法按题目要求让两只松鼠均成功收集糖果。
故输出 $0$。
**样例 3 解释：**
请注意，需输出方案数对 $998244353$ 取模的结果。
### 约束条件
* $2 \leq N \leq 2 \times 10^5$
* $1 \leq P_i \leq N$
* $1 \leq C_i \leq 10^9$
* $1 \leq D_i$
* $D_1 + D_2 + \cdots + D_N \leq 10^6$
* 所有输入值均为整数。
* $T$ 是一棵以顶点 $1$ 为根的有根树。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？