7277 - 挖迷宫（laby）
勇者们马上要攻击作为魔王的你，但你的地下迷宫还没有挖好，且只有一个迷宫的入口。
迷宫由n个洞穴组成，其中1号洞穴为迷宫的入口，由n-1条道路连通整个迷宫中的所有洞穴，这些道路还未挖掘。不过这些道路有长有短，对于连接洞穴u_i、v_i之间的道路，还需要r_i天才能挖通。每天可以选择一个未挖通的道路挖掘，且此道路连接着某个已挖通的洞穴，在已挖通的迷宫中移动的时间忽略不计（洞穴是天然存在的，不用花时间去挖掘）。
另外为了能够及时获得洞穴中的魔力以对付勇者，你还计划需要在第d_i天前(包括第d_i天)抵达第i个洞穴。现在是第1天，你想知道你的计划能否实现。
输入
每个测试点包含多组测试数据。
第一行包含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天。
输出
输出t行，每行输出 “Yes”或者“No”，表示能否及时抵达各个洞穴。
样例
输入
1 5 0 1 2 3 4 1 2 1 1 3 1 2 4 1 4 5 1
输出
Yes
输入
3 37 0 151 1966 3557 1008 583 1295 1813 2357 544 1915 2325 1160 1445 2832 2660 199 3079 2785 1016 3106 2739 3013 2953 1594 1264 1897 1816 3480 448 2365 1494 2256 2898 2985 3337 3575 33 19 19 8 36 96 20 33 91 23 24 19 26 3 29 33 9 70 3 8 29 3 37 50 14 35 75 35 27 87 22 35 84 35 28 58 29 33 9 33 32 16 35 1 60 13 2 52 7 28 51 8 15 19 10 3 92 34 21 49 30 34 45 13 33 86 12 6 65 25 19 4 33 5 28 11 2 20 7 4 1 17 19 65 22 13 10 33 24 53 5 16 72 23 3 88 31 5 48 22 18 94 6 22 66 21 35 63 15 0 1206 87 360 331 1228 1051 1189 1234 293 1216 865 1295 1485 1202 5 9 86 15 13 73 1 10 35 6 10 19 3 13 72 3 4 52 11 7 12 6 8 86 5 4 49 5 7 13 7 14 29 7 6 51 1 12 13 10 2 41 36 0 3476 3255 3371 3498 98 2559 2672 1610 1533 3201 2248 1397 2369 384 704 239 1811 3586 64 893 75 2552 1689 3190 1670 3416 354 3593 2713 38 2211 163 858 402 2701 19 21 91 18 27 50 9 15 19 19 7 70 19 11 37 14 21 73 14 32 41 1 24 73 32 25 90 19 13 62 18 16 82 22 2 80 17 12 13 29 6 1 21 10 20 31 3 87 21 20 56 4 35 98 12 24 90 2 15 86 3 7 44 21 6 21 10 18 72 10 36 34 11 1 17 2 35 5 5 30 60 22 36 37 30 11 33 26 6 31 34 33 90 19 33 20 33 8 62 2 28 6 23 6 40
输出
No No No
输入
4 48 0 2923 951 3412 177 2749 798 3025 690 3763 3776 1286 980 1079 2314 2985 3923 2929 1353 3871 4187 438 40 1662 4339 1807 1779 3960 3488 2518 1440 305 1590 4194 3450 330 4021 3871 2403 3834 2846 923 570 2511 664 1665 3457 576 37 40 76 27 7 10 18 46 92 1 38 64 7 38 38 42 23 50 45 19 60 5 3 72 11 20 80 47 40 68 6 41 13 48 14 72 44 4 69 14 27 44 46 39 33 36 37 92 15 24 74 6 33 24 34 14 32 36 39 60 47 17 48 6 2 38 10 37 44 9 14 100 14 33 16 10 35 74 7 28 48 37 16 93 15 44 5 5 37 20 39 12 77 30 21 6 26 33 25 47 29 52 43 10 48 15 40 13 42 20 65 13 11 42 8 26 44 8 31 32 45 17 76 32 7 65 32 25 74 22 11 86 7 21 50 37 33 21 47 11 30 15 0 207 1471 815 589 773 1432 1243 996 1094 947 866 1352 676 934 12 15 15 15 2 89 5 15 43 3 10 25 1 11 84 4 5 69 6 11 90 5 11 41 13 3 21 3 5 90 7 3 2 15 9 31 15 14 37 8 2 18 5 0 45 79 38 454 5 4 93 1 3 30 1 2 100 4 3 88 37 0 1017 79 681 3574 3470 3557 1069 1483 358 3274 2524 1206 1728 1500 2599 2715 1021 1586 2419 1737 3511 2423 3393 1693 60 1967 1562 1765 3365 2344 406 410 64 1832 3278 3435 8 30 96 26 20 15 10 29 83 32 27 43 27 3 73 12 16 77 14 22 47 19 2 71 16 15 56 19 30 48 26 27 87 4 24 94 5 3 80 14 12 91 17 25 77 22 26 54 23 8 39 37 33 83 25 7 46 21 25 36 13 3 25 36 35 52 23 18 94 33 28 31 24 34 39 28 26 89 11 6 86 18 10 73 2 31 14 24 26 75 8 1 67 8 11 100 18 22 81 9 27 5 27 35 88 25 23 2
输出
No No No No
提示
【样例1解释】
样例包含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已挖通。
第四天挖掘洞穴2和洞穴3之间的道路。正好在第4天抵达洞穴5。
所有洞穴都能在计划时间内抵达。
【数据范围】
对于所有测试数据有：1≤t≤10,1≤n≤10^5,0≤r_i≤10^9,1≤d_i≤10^9
来源
云南精英赛