bzoj#P4054. [Cerc2013] Escape

[Cerc2013] Escape

题目描述

一棵树上,勇者在 11 号点,初始血量是 00

每个点有一个权值,踩上去血量会加上 Δi\Delta_i ,这个值可正可负。

勇者任何时候血量不能低于 00,问勇者能否到达某个目标点 tt

输入格式

第一行一个整数 TT 表示测试数据组数。

对于每一组数据的第一行输入两个数 nntt 分别表示节点数和勇者必须到达的点。

接下来是 nn 个整数,表示每个节点的权值。

接下来 n1n - 1 行,每行两个数 aabb 代表一条边连接的两个节点。

输出格式

对于每个测试用例输出一行,如果勇者能够到达目标点输出 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 

数据规模与约定

对于 100%100\% 的数据满足,1n2×1051 \le n \le 2 \times 10 ^ 56Δi1066\le \Delta_i \le 10^6