#4054. [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

数据范围与提示