[Cerc2013]Escape

内存限制：128 MiB 时间限制：10 Sec

提交提交记录讨论

一棵树上，勇者在1号点，初始血量是0。每个点有一个权值，踩上去血量会加上deltai，这个值可正可负。勇者任何时候血量不能低于0。问勇者能否到达某个目标点T。

国际惯例1≤n≤2*10^5,　6≤deltai≤10^6

样例输入


			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