#P4054. [Cerc2013]Escape

[Cerc2013]Escape

题目描述

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

每个房间 ii 有一个整数 Δi\Delta_i。勇者可以重复经过同一房间,但只在第一次到达时把血量增加 Δi\Delta_i。初始在 11 号房间时也要结算,首次到达出口时也要先结算,再判断是否成功。

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

输入格式

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

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

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

接下来 n−1n - 1 行,每行两个数 aa 和 bb 代表一条边连接的两个节点。

输出格式

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

数据规模与约定

对于 100%100\% 的数据满足,2≤n≤2×1052\le n\le2\times10^5,2≤t≤n2\le t\le n,−106≤Δi≤106-10^6\le\Delta_i\le10^6,且 Δ1≥0\Delta_1\ge0。

题目来源