bzoj#P4054. [Cerc2013] Escape
[Cerc2013] Escape
题目描述
一棵树上,勇者在 号点,初始血量是 。
每个点有一个权值,踩上去血量会加上 ,这个值可正可负。
勇者任何时候血量不能低于 ,问勇者能否到达某个目标点 。
输入格式
第一行一个整数 表示测试数据组数。
对于每一组数据的第一行输入两个数 和 分别表示节点数和勇者必须到达的点。
接下来是 个整数,表示每个节点的权值。
接下来 行,每行两个数 和 代表一条边连接的两个节点。
输出格式
对于每个测试用例输出一行,如果勇者能够到达目标点输出 escaped
否则输出 trapped
。
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
数据规模与约定
对于 的数据满足,,。