#4054. [Cerc2013]Escape

题目描述

一棵树上，勇者在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 

数据范围与提示