Dragons
Description
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 $N$ nodes, indexed form $1$ to $N$, each node representing fortifications of varying heights. The height of fortification $i$ is denoted as $h_i$.
The dragon has a power level of $P$ and starts flying at the base of fortification $u$ (i. e. its initial height is $0$). Its goal is to attack fortification $v$. It flies along the path from $u$ to $v$ and when it encounters a fortification $x$ with a height $h_x$ greater than or equal to its current height, it loses $h_x$ points from its power and continues flying at a height of $h_x$.
Unfortunately, there's a bug in the game: if the dragon's current power $P_{crt}$ becomes less than $0$, it immediately becomes $-P_{crt}$. You have the ability to shuffle the fortifications along the path from $u$ to $v$. Your objective is to find an arrangement such that the dragon's power is reduced to $0$ when it reaches fortification $v$, preventing the dragon from attacking it.
Being given $Q$ scenarios $(u, v, P)$, you should find if it's possible to shuffle the fortifications along the path from $u$ from $v$ so the dragon won't attack the tower $v$.
The first line contains one integer $N$ ($2 \leq N \leq 10^4)$, the number of nodes. The second line contains $N$ integers $h_1$, $h_2$, $\dots$, $h_N \ (1 \leq h_i \leq 10^3)$.
Each of the following $N - 1$ lines contains two integers $u$ and $v \ (1 \leq u, v \leq N)$, meaning that there is an edge between $u$ and $v$.
The next line contains one integer $Q$ ($1 \leq Q \leq 10^4)$, the number of scenarios. Each of the next $Q$ lines contains three integers $u$, $v \ (1 \leq u, v \leq N)$ and $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.
Input
The first line contains one integer $N$ ($2 \leq N \leq 10^4)$, the number of nodes. The second line contains $N$ integers $h_1$, $h_2$, $\dots$, $h_N \ (1 \leq h_i \leq 10^3)$.
Each of the following $N - 1$ lines contains two integers $u$ and $v \ (1 \leq u, v \leq N)$, meaning that there is an edge between $u$ and $v$.
The next line contains one integer $Q$ ($1 \leq Q \leq 10^4)$, the number of scenarios. Each of the next $Q$ lines contains three integers $u$, $v \ (1 \leq u, v \leq N)$ and $P \ (1 \leq P \leq 10^3)$ describing a scenario.
Output
For each scenario, output $"$YES$"$ if it's possible to shuffle the fortifications so the dragon won't attack, or $"$NO$"$ otherwise.
9
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
3
5 7 13
5 7 1
9 8 12
YES
NO
YES