PikaPika

All submissions for this problem are available.
It's battle time and Pikachu has to win this time. Ash is ready with his challenge, and this time the challenge is to collect maximum Pokecoins. Ash has laid down $N$ Pokestops, each with a unique label from $1$ to $N$ and exactly one Pokecoin. There are $N1$ roads laid down, such that there exists a path from each Pokestop to every other Pokestop. The Pokecoin at $ith$ Pokestop is guarded by a Pokemon of strength $S_{i}$. Pikachu makes a total of $Q$ trips, the $ith$ trip being the simple path from Pokestop $U_{i}$ to Pokestop $V_{i}$. For the $ith$ trip, Pikachu has been given a new shield with strength $X_{i}$. He has to get maximum number of Pokecoins by defeating the guards. Each time Pikachu defeats the guard at $ith$ Pokestop, his shield strength gets reduced by $S_{i}$. He can collect a coin from the $ith$ Pokestop only if he defeats the pokemon guarding it. Help Pikachu to find the maximum number of coins for each trip if he uses the optimal strategy. **Note**:  All trips are independent.  The strengths of pokemons guarding the pokestops does not change.  Pikachu can defeat a pokemon only if the pokemon's strength does not exceed the sheild strength. ###Input:  The first line of input contains $N$, denoting the number of nodes in the tree.  Next line contains $N$ space separated integers, denoting the strengths of the pokemons guarding the pokestops.  Each of the next $N1$ lines contains two integers $U$ and $V$, denoting an edge between the nodes $U$ and $V$.  Next line contains $Q$, denoting the number of queries.  Each query contains three space separated integers denoting $U$,$V$ and $X$ respectively. ###Output: For each query, output a single integer as explained above. ###Constraints  $1 \leq N,Q \leq 10^5$  $1 \leq U[i],V[i] \leq N $  $1 \leq S[i] \leq 10^5 $  $0 \leq X[i] \leq 10^9 $ ###Sample Input: 3 5 5 3 1 2 2 3 1 1 3 9 ###Sample Output: 2 ###EXPLANATION: The strengths of pokemons on the path from $1$ to $3$ are $5$, $5$, and $3$. Pikachu can defeat at max $2$ of them with strengths $(5,3)$.Author:  enigma27 
Tags  enigma27 
Date Added:  3032019 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions