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）。

输入输出样例 #1

输入 #1

8
1 2 0 3
2 1 3 3
1 2 0 4
4 1 2 2
1 2 0 5
6 1 5 5
5 1 140 1

输出 #1

Yes

输入输出样例 #2

输入 #2

12
1 1 166 619
1 1 17 592
2 1 222 983
2 1 729 338
5 1 747 62
3 1 452 815
3 2 0 1
4 2 0 40
4 1 306 520
6 1 317 591
1 1 507 946

输出 #2

No

输入输出样例 #3

输入 #3

12
1 1 1 791
2 2 0 410
2 1 724 790
2 1 828 599
5 2 0 13
3 1 550 803
1 1 802 506
5 1 261 587
6 1 663 329
8 1 11 955
9 1 148 917

输出 #3

Yes

输入输出样例 #4

输入 #4

12
1 2 0 1000000000
2 2 0 1000000000
3 2 0 1000000000
4 2 0 1000000000
5 2 0 1000000000
6 2 0 1000000000
7 2 0 1000000000
8 2 0 1000000000
9 2 0 1000000000
10 2 0 1000000000
11 1 1 1

输出 #4

Yes

说明/提示

限制条件

• $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 翻译