题目描述

You hit the emperor lich with full force and slay it. There is a stair leading upwards here. You climb upstairs. You drink from the pool. You feel much better. The karmic lizard punches through your armor and hits you. You die...

After an epic fight with the emperor lich, the hero struggles to escape the dungeon consisting of $n$ chambers and $n − 1$ corridors connecting them. He starts in chamber number $1$ and must reach chamber number $t$ , moving only along the corridors. All chambers are reachable from chamber number $1$ . Bruised after the last fight, the hero starts the journey with $0$ hit-points $(HP).$ These points represent his health $-$ if ever they fall below zero, the hero's story ends there as a tragic one.

In some chambers there are monsters $-$ a monster must be fought, and it always manages to take some of the hero's HP. In some other chambers there are magic pools $-$ every pool restores some number of the hit-points. There is no upper limit on the hero's health. Every chamber can be visited multiple times, but the gain or loss of HP happens only once, on the very first visit.

Determine whether the hero can escape the dungeon alive.

输入格式

The first line of input contains the number of test cases $T$ . The descriptions of the test cases follow:

The first line of each test case contains two integers: the number of chambers $n , 2 \le n \le 200 000$ , and the number of the exit chamber $t , 2 \le t \le n$ . The second line contains $n$ space separated integers between $-10^{6}$ and $10^{6} -$ the i-th of them denotes the HP gain in the i-th chamber (negative denotes a monster, positive $-$ a pool, and zero means that the chamber is empty). The first chamber does not contain a monster, but a pool is possible there. The exit chamber may contain a pool or a monster, and the monster will have to be fought before escaping.

The next $n−1$ lines contain the descriptions of corridors. Each one contains a pair of integers $-$ the ends of a corridor.

输出格式

For each test case print a single line containing the word escaped if escape is possible, or trapped otherwise.

题目大意

题目背景

在经历和巫妖王史诗级别的战斗后，英雄们想要从地牢中逃走。

题目描述

这个地牢是由 $n$ 个房间和 $n-1$ 条走廊连接组成的树状结构，英雄一开始在 $1$ 号房间，而且他只有抵达 $t$ 号房间才能逃离这个地牢。从 $1$ 号房间出发可以抵达任何一个其它的房间，可惜的是，在经历激烈的战斗后，英雄的精力使用完了，所以一开始该英雄的精力为 $0$，并且一旦英雄的精力低于 $0$，那么英雄就会当场逝世，以悲剧结束。在这些房间中，里面暗藏玄机，里面可能有怪兽，也有可能是可以补充精力的魔泉，当然也可能什么也没有，如果是怪兽，那么英雄就必须与它战斗从而消耗一些精力，如果是魔泉，那么英雄可以补充自己的精力。所有的怪兽只会战斗一次，所有的魔泉只能使用一次。（换句话说就是所有的精力的上升或者下降只会发生在第一次访问这个房间的时候）

英雄的精力没有上限，每一个房间都可以反复走多次。

输入格式

输入包括多组数据，第一行表示测试的数据的组数 $T$。

每一个测试用例的第 $1$ 行都包括两个整数 $n$ $(2 \le n \le 200000 )$ 和 $t$ $(2 \le t \le n)$，分别表示地牢的房间的数量和英雄必须到达的房间号。第二行是 $n$ 个整数，代表了 $n$ 个房间的情况，其中第 $i$ 个数代表了第 $i$ 个房间情况，所有的数的绝对值都不大于 $10^{6}$。如果该数是负数，表明该房间里面有怪兽，精力会减少，如果是正数，表明房间里面有魔泉，可以补充精力，如果是 $0$，表明房间里面空空如也。注意 $1$ 号房间不会有怪兽，但是有可能会有魔泉，$t$ 号房间可能怪兽或者魔泉，如果是怪兽，那么英雄必须要击败怪兽才能逃离。

在接下来的 $n-1$ 行中，每行两个整数 $a$ 和 $b$ ，表示房间 $a, b$ 之间有一条走廊连接。

输出格式

对于每一个测试用例都单行输出：

如果英雄能够逃脱，那么输出 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

提示

Time limit: 8 s, Memory limit: 128 MB.