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^4Ki​≤104.

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}ith 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}ith query, you are given three integers:

• X_iXi​ T_iTi​ K_iKi​ : Find the minimum number of seconds after which, there are at least T_iTi​ nodes with energy not less than K_iKi​ on the path from node $1$ to node X_iXi​. If it is not possible to have at least T_iTi​ nodes with energy not less than K_iKi​ on the path from node $1$ to node X_iXi​ 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 = 1Ai​=1, it means that the i^{th}ith node is energetic, otherwise the i^{th}ith node is not energetic.
• The next $N-1$ lines describe the edges. The i^{th}ith of these $N-1$ lines contains two space-separated integers U_iUi​ and V_iVi​, denoting an edge between U_iUi​ and V_iVi​.
• 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_iXi​,Ti​,Ki​, the query.

Output Format

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

Constraints

Sample 1:

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}1st 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}2nd 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}3rd 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$.