624. 与非门树

单点时限: 1.0 sec

内存限制: 512 MB

QQ小方以前不会做与非门的实验,现在他会了,所以他急切的想教会你。

同一个与非门可能有多个输入接口,但只会有一个输出接口,由于实验箱的限制,只能将与非门连接成了一个树形结构,即某个与非门的输出,会唯一的连接另一个与非门的一个输入上,各个输入之间互不影响,有唯一的一个与非门(树根)的输出只连接到了一个 LED 上,表示整个电路的输出,“空着”(没有连接到其他输出)的输入接口均连接了一个开关,表示一个输入($0$ 或 $1$)。

单单讲给你听肯定是不够的,为了表现自己,QQ小方现在要考考你。

QQ小方正在做数字逻辑实验,QQ小方今天的任务是用一堆与非门实现一个逻辑电路。

对于一个正常运作的与非门,当且仅当所有输入为 $1$ 时,与非门输出 $0$,否则与非门输出 $1$。但是很可惜,由于实验室设备陈旧,其中有一些与非门早就被烧坏了,无论他们的输入是什么,他们都会保持某一种输出(即永远输出 $0$ 或 $1$ 的其中一种)。

现在QQ小方想知道电路对于多少种可能的输入(即所有开关的状态)会得到正确的输出。QQ小方当然正确连接了电路。

为了不为难你,QQ小方测试了每个与非门的好坏,并把情况以及整个树的结构告诉了你,希望你能帮他看看现在他对于多少比例有正确的输出,结果模 $998~244~353$ 。

输入格式

第一行包含一个整数 $n(1 \leq n \leq 200~000)$ 表示与非门的总数。

接下来的 $n$ 行中,第 $i+1$ 行包含三个整数 $f_i, g_i, h_i(0 \leq f_i \leq n,1 \leq g_i \leq 1~000~000~000,h_i \in {-1, 0, 1})$,$f_i$ 表示第 $i$ 个与非门的输出接在了 $f_i$ 的输入端口上,$g_i$ 表示第 $i$ 个与非门的输入端口数,每个连接都独占某个输入端口,保证不会出现冲突的连接,$h_i = -1$ 表示这个与非门正常工作,$h_i = 0, 1$ 表示其永远输出 0 或 1。

存在唯一的 $f_i = 0$ 表示第 $i$ 个与非门的输出是整个电路的输出,保证联通且呈树形,不存在环。

输出格式

输出一个整数 $X$ 表示输出正确的比例。$0 \leq X \leq 998~244~352$

假设正确答案比例的分数是 $\frac{P}{Q}$ 则 $X = P \cdot Q^{-1}$ 即 $X \cdot Q \equiv P \pmod{998244353}$。

样例

Input
3
0 2 -1
1 1 1
1 1 -1
Output
249561089

提示

样例解释

$249561089 \cdot 4 \equiv 3 \pmod{998244353}$

8 人解决,17 人已尝试。

8 份提交通过,共有 46 份提交。

7.4 EMB 奖励。

创建: 2 年,5 月前.

修改: 1 年,2 月前.

最后提交: 3 周,5 天前.

来源: N/A

题目标签