New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Connect The Villages

Contributed by

Akhilesh Singh Bhadauria

Hard

0/120

Avg time to solve 90 mins

Success Rate 30 %

0 upvotes

Problem Statement

You are the road constructor in charge in a country of ‘N’ villages. There are ‘N’ - 1 roads which are represented by ‘U’, ‘V’, and ‘W’. Which represents there is a road between village ‘U’ and Village ‘V’ and ‘W’ represents the distance between village ‘U’ and ‘V’.

There was a meeting scheduled between people of these ‘N’ villages and they came up with ‘Q’ questions.

Each question is of the following format :

U V W

This represents if we connect village ‘U’ with village ‘V’ directly with a road of distance ‘W’ and remove anyone already connected road from the village in such a way that villages stay connected.

You have to tell whether after adding the current road, the total sum of all the distances of roads is strictly lesser than the previous sum of all the distances of the roads.

Example:

Input: ‘N’ = 4, ‘ROADS’ = [[1, 2, 2], [1, 3, 3], [2, 4, 3]], ‘Q’ = 1, ‘Queries’ = [[3, 4, 2]]
Output: YES
If we remove the road between 2 and 4 and add the current road of queries then the sum becomes 7 which previously was 8.

Detailed explanation ( Input/output format, Notes, Constraints, Images )

Input Format :

The first line will contain the integer 'T', denoting the number of test cases.
The next line contains a single integer ‘N’ representing the number of villages.
The next ‘N’-1 lines contain three integers ‘U’, ‘V’, and ‘W’ representing the villages ‘U’ and ‘V’ where a road of distance ‘W’ is made.
The next line contains an integer ‘Q’ representing the number of queries.
The next ‘Q’ lines contain ‘U’, ‘V’, and ‘W’ representing the query of making a road between villages ‘U’, ‘V’ with a distance ‘W’.

Output format :

For each test query, you should output ‘YES’ if the total distance strictly reduces else print ‘NO’.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10^5
1 <= W <= 10^9
1 <= U, V <= N
1 <= Q <= 10^5

Time Limit: 1 sec

Sample Input 1 :

Sample Output 1 :

YES
YES NO

Explanation Of Sample Input 1 :

For the first test case:-
If we remove the road between 2 and 4 and add the current road of query then the sum becomes 6 which previously was 8 so the answer is ‘YES’.

For the second test case:-
Initially, the total distance is 9.
For the first query if we add the road between villages 1 and 3 with the distance 2 and remove the road between 2 and 3 which has a distance of 5 so now the total distance of all the roads is 6 which is less than 9 so the answer is ‘YES’.
For the second query, the initial road between 1 and 2 has a distance of 4 but now we are trying to create a road of distance 5 which will increase the total distance to 10 so the answer is ‘NO’.

Sample Input 2 :

Sample Output 2 :

YES NO YES NO
NO NO NO NO NO

Auto

Console