#P4054. [Cerc2013]Escape
[Cerc2013]Escape
题目描述
一棵树上,勇者在 号点,初始血量是 。
每个房间 有一个整数 。勇者可以重复经过同一房间,但只在第一次到达时把血量增加 。初始在 号房间时也要结算,首次到达出口时也要先结算,再判断是否成功。
勇者任何时候血量不能低于 ,问勇者能否到达某个目标点 。
输入格式
第一行一个整数 表示测试数据组数。
对于每一组数据的第一行输入两个数 和 分别表示节点数和勇者必须到达的点。
接下来是 个整数,表示每个节点的权值。
接下来 行,每行两个数 和 代表一条边连接的两个节点。
输出格式
对于每个测试用例输出一行,如果勇者能够活着到达出口,输出 escaped,否则输出 trapped。
2
7 7
0 -3 2 2 3 -4 0
1 2
2 3
2 4
1 5
5 6
6 7
3 2
3 3 -4
1 3
2 3
escaped
trapped
数据规模与约定
对于 的数据满足,,,,且 。