[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.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

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$.