# Energetic Node(Easy Version) Codechef Solution

### We Are Discuss About CODECHEF SOLUTION

Energetic Node(Easy Version) Codechef Solution

## Problem

This is the easy version of the problem. The only difference is that, in this version, K_i \leq 10^4.

There’s a tree having N nodes, out of which, some nodes are energetic.

Initially, energy of all the nodes is 0. In the i^{th} second, every energetic node will make the energy of itself and all its neighbours increase by i.

You need to answer Q queries. For the i^{th} query, you are given three integers:

• X_i T_i K_i : Find the minimum number of seconds after which, there are at least T_i nodes with energy not less than K_i on the path from node 1 to node X_i. If it is not possible to have at least T_i nodes with energy not less than K_i on the path from node 1 to node X_i after any amount of time, print -1 instead.

### Input Format

• The first line contains an integer N — the number of nodes.
• The second line contains N space-separated integers, the array A denoting whether the nodes are energetic. If A_i = 1, it means that the i^{th} node is energetic, otherwise the i^{th} node is not energetic.
• The next N-1 lines describe the edges. The i^{th} of these N-1 lines contains two space-separated integers U_i and V_i, denoting an edge between U_i and V_i.
• The next line contains an integer Q — the number of queries.
• The next Q lines contain three space-separated integers X_i,T_i,K_i, the query.

### Output Format

For each query, output on a new line: the minimum number of seconds after which, there are at least T_i nodes with energy not less than K_i on the path from node 1 to node X_i.
If it is not possible to have at least T_i nodes with energy not less than K_i on the path from node 1 to node X_i after any amount of time, print -1 instead.

### Constraints

• 1 \leq N,Q \leq 4\cdot 10^4
• 0 \leq A_i\leq 1
• 1 \leq U_i, V_i,X_i,T_i \leq N
• 1 \leq K_i \leq 10^4

### Sample 1:

Input

Output

7
1 0 1 0 0 1 0
1 2
1 3
1 4
3 5
3 6
4 7
4
7 3 1
6 3 2
7 2 3
5 3 5
-1
1
2
3

### Explanation:

Query 1: No matter how long, there will not be at least 3 nodes having energy not less than 1 on the path from node 1 to node 7. Thus, the answer is -1.

Query 2: In the 1^{st} second, the energy of nodes 1,3, and 6 becomes 2,3, and 2 respectively. Thus, there are at least 3 nodes with energy not less than 2.

Query 3: In the 2^{nd} second, the energy of nodes 1,4, and 7 becomes 6,3, and 0 respectively. Thus, there are at least 2 nodes with energy not less than 3.

Query 4: In the 3^{rd} second, the energy of nodes 1,3, and 5 is 12,18, and 6 respectively. Thus, there are at least 3 nodes with energy not less than 5.

## SOLUTION

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here ScishowEngineer   Then Follow US HERE and Join Telegram.