No testdata at current.

题目描述

勇者们马上要攻击作为魔王的你，但你的地下迷宫还没有挖好，且只有一个迷宫的入口。

迷宫由 $n$ 个洞穴组成，其中 $1$ 号洞穴为迷宫的入口，由 $n-1$ 条道路连通整个迷宫中的所有洞穴，这些道路还未挖掘。不过这些道路有长有短，对于连接洞穴 $u_i$、$v_i$ 之间的道路，还需要 $r_i$ 天才能挖通。每天可以选择一个未挖通的道路挖掘，且此道路连接着某个已挖通的洞穴，在已挖通的迷宫中移动的时间忽略不计（洞穴是天然存在的，不用花时间去挖掘）。

另外为了能够及时获得洞穴中的魔力以对付勇者，你还计划需要在第 $d_i$ 天前（包括第 $d_i$ 天）抵达第 $i$ 个洞穴。现在是第 $1$ 天，你想知道你的计划能否实现。

输入格式

从文件 laby.in 中读入数据。 每个测试点包含多组测试数据。 第一行包含 $1$ 个数字 $t$，表示测试数据的组数。 每组测试数据的第一行包含一个整数 $n$，表示洞穴的数量。 接下来一行包含 $n$ 个数字，第 $i$ 个数字表示，第 $i$ 个洞穴最晚需要在第 $d_i$ 天抵达。保证第一个数字为 $0$。 接下来 $n-1$ 行，每行包含 $3$ 个数字 $u_i$、$v_i$、$r_i$。表示第 $i$ 条道路连接 $u_i$、$v_i$ 两个洞穴，这条道路需要挖 $r_i$ 天。

输出格式

输出到文件 laby.out 中。 输出 $t$ 行，每行输出 “Yes” 或者 “No”，表示能否及时抵达各个洞穴。

样例输入

1
5
0 1 2 3 4
1 2 1
1 3 1
2 4 1
4 5 1 

Yes

样例解释

样例包含 $1$ 组测试数据。迷宫情况如下图，每条道路均需要花 $1$ 天的时间挖掘，第 $2$ 个洞穴需要在第 $1$ 天之前抵达，第 $3$ 个洞穴需要在第 $2$ 天之前抵达，第 $4$ 个洞穴需要在第 $3$ 天之前抵达，第 $5$ 个洞穴需要在第 $4$ 天之前抵达。

能够及时抵达的方案只有一种。 第一天挖掘洞穴 $1$ 和洞穴 $2$ 之间的道路。正好抵达洞穴 $2$，洞穴 $1$、$2$ 已挖通。 第二天挖掘洞穴 $1$ 和洞穴 $3$ 之间的道路。正好在第 $2$ 天抵达洞穴 $3$，洞穴 $1$、$2$、$3$ 已挖通。 第三天挖掘洞穴 $2$ 和洞穴 $4$ 之间的道路。正好在第 $3$ 天抵达洞穴 $4$，洞穴 $1$、$2$、$3$、$4$ 已挖通。 第四天挖掘洞穴 $4$ 和 $5$ 之间的道路。正好在第 $4$ 天抵达洞穴 $5$。 所有洞穴都能在计划时间内抵达。

数据范围

对于所有测试数据有： $1\le t\le 10$， $1\le n\le 10^5$， $0\le r_i\le 10^9$， $1\le d_i\le 10^9$。

特殊性质

A：$r_i=1$ B：所有道路的两个洞穴编号均满足，$u_i=v_i+1$ C：所有洞穴的所需抵达时间 $d_i$ 均相同，$d_i=d_j$ D：所有道路的其中一个洞穴均为洞穴 $1$，$u_i=1$。