AT_abc319_f.[ABC319F] Fighter Takahashi

有一棵包含 $N$ 个顶点的树。第 $1$ 个顶点是根，对于每个 $i$（$2\leq i\leq N$），第 $i$ 个顶点的父节点是 $p_i$（$1\leq p_i<i$）。

对于非根节点，每个顶点上要么放置了“敌人”，要么放置了“药”。高桥君想要击败所有的敌人。最开始，高桥君的强度为 $1$，并且位于顶点 $1$。对于 $i=2,\ldots,N$，第 $i$ 个顶点的信息用整数三元组 $(t_i,s_i,g_i)$ 表示，具体如下：

• 如果 $t_i=1$，则第 $i$ 个顶点上有敌人。当高桥君第一次到达该顶点时，如果他的强度小于 $s_i$，则会被敌人击败并“失败”，之后无法移动到其他顶点。否则，高桥君可以击败敌人，并且强度增加 $g_i$。
• 如果 $t_i=2$，则第 $i$ 个顶点上有药。当高桥君第一次到达该顶点时，他会喝下药水，强度变为原来的 $g_i$ 倍。（此时 $s_i=0$。）

含有药的顶点最多不超过 $10$ 个。

高桥君可以在相邻的顶点之间移动。请判断高桥君是否能够击败所有的敌人。

输入按以下格式从标准输入读入。

$N$
$p_2\ t_2\ s_2\ g_2$
$p_3\ t_3\ s_3\ g_3$
$\vdots$
$p_N\ t_N\ s_N\ g_N$

请输出一行答案（Yes 或 No）。

限制条件

• $2\leq N\leq 500$
• $1\leq p_i<i\ (2\leq i\leq N)$
• $t_i\in\lbrace1,2\rbrace\ (2\leq i\leq N)$
• 若 $t_i=1$，则 $1\leq s_i\leq 10^9\ (2\leq i\leq N)$
• 若 $t_i=2$，则 $s_i=0\ (2\leq i\leq N)$
• $1\leq g_i\leq 10^9\ (2\leq i\leq N)$
• 含有药的顶点最多 $10$ 个
• 所有输入均为整数

样例解释 1

最初，树的结构如下图所示。

高桥君可以按照 $1,2,3,2,1,6,7,6,1,4,5,8$ 的顺序移动，从而击败所有敌人。此时高桥君所在的顶点和强度的变化如下图所示（图中省略了已经访问过的顶点的移动）。

例如，如果高桥君从顶点 $1$ 按 $4,5,8$ 的顺序移动，则到达顶点 $8$ 时强度小于 $s_8=140$，因此会失败，无法击败所有敌人。

由 ChatGPT 4.1 翻译