← 返回题目列表

AtCoder · abc319_f

I. 高桥战斗机

中文机器翻译题面 查看原题

分数: 550 点

问题陈述

有一棵树 N 顶点。 的 1-st 顶点是根,是 i- 第一个顶点 (2\leq i\leq N) is p _ i\ (1\leq p _ i\lt i).

每个非根顶点都有一个 敌人 或 医药 就可以了。 高桥想要打败所有的敌人。 最初他的实力是 1,他在顶点 1。 对于 i=2,\ldots,N的信息 i-th 顶点由整数三元组表示 (t _ i,s _ i,g _ i) 如下。

  • If t _ i=1,有一个敌人 i- 第一个顶点。当高桥第一次访问这个顶点时,如果他的力量小于 s _ i,高桥被敌人击败, 输了,之后他无法移动到其他顶点。否则,他击败敌人,他的力量增加 g _ i.
  • If t _ i=2,那里有一种药 i- 第一个顶点。当高桥第一次造访这个顶点时,他服用了药物,他的力量乘以 g _ i。 (对于带有药物的顶点, s _ i=0.)

最多有 10 顶点用药。

Takahashi 可以重复移动到相邻顶点。 确定他是否可以击败所有敌人。

约束

  • 2\leq N\leq 500
  • 1\leq p _ i\lt i\ (2\leq i\leq N)
  • t _ i\in\lbrace1,2\rbrace\ (2\leq i\leq N)
  • t _ i=1\implies1\leq s _ i\leq 10 ^ 9\ (2\leq i\leq N)
  • t _ i=2\implies s _ i=0\ (2\leq i\leq N)
  • 1\leq g _ i\leq 10 ^ 9\ (2\leq i\leq N)
  • 最多有 10 顶点 t _ i=2.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

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 or No)在一行中。


示例输入 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

最初,树看起来像这样:

高桥可以通过从顶点移动来击败所有敌人 1 to 2,3,2,1,6,7,6,1,4,5,8 按此顺序。 这里,他的位置和强度变化如下图所示(已访问过的顶点的移动被省略)。

另一方面,如果他从顶点移动 1 to 4,5,8 按照这个顺序,例如,他访问顶点时的强度 8 将小于 s _ 8=140,所以他没有打败所有敌人就输了。


示例输入 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

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

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