M. Dragons

Time limit: 2.5s Memory limit: 256MB Input: Output:

You are playing a game in which you must defend your village from a dragon.

The village can be represented as a tree (a connected acyclic graph) with NN nodes, indexed form 11 to NN, each node representing fortifications of varying heights. The height of fortification ii is denoted as hih_i.

The dragon has a power level of PP and starts flying at the base of fortification uu (i. e. its initial height is 00). Its goal is to attack fortification vv. It flies along the path from uu to vv and when it encounters a fortification xx with a height hxh_x greater than or equal to its current height, it loses hxh_x points from its power and continues flying at a height of hxh_x.

Unfortunately, there's a bug in the game: if the dragon's current power PcrtP_{crt} becomes less than 00, it immediately becomes Pcrt-P_{crt}. You have the ability to shuffle the fortifications along the path from uu to vv. Your objective is to find an arrangement such that the dragon's power is reduced to 00 when it reaches fortification vv, preventing the dragon from attacking it.

Being given QQ scenarios (u,v,P)(u, v, P), you should find if it's possible to shuffle the fortifications along the path from uu from vv so the dragon won't attack the tower vv.


The first line contains one integer NN (2N104)2 \leq N \leq 10^4), the number of nodes. The second line contains NN integers h1h_1, h2h_2, \dots, hN (1hi103)h_N \ (1 \leq h_i \leq 10^3).

Each of the following N1N - 1 lines contains two integers uu and v (1u,vN)v \ (1 \leq u, v \leq N), meaning that there is an edge between uu and vv.

The next line contains one integer QQ (1Q104)1 \leq Q \leq 10^4), the number of scenarios. Each of the next QQ lines contains three integers uu, v (1u,vN)v \ (1 \leq u, v \leq N) and P (1P103)P \ (1 \leq P \leq 10^3) describing a scenario.


For each scenario, output "YES" if it's possible to shuffle the fortifications so the dragon won't attack, or "NO" otherwise.



1 2 3 4 5 6 7 8 9
1 2
1 3
1 4
2 5
3 6
3 7
4 8
6 9
5 7 13
5 7 1
9 8 12



Log in or sign up to be able to send submissions!