Update appNew update is available. Click here to update.
sidenav-btnClose
Topic list
Connect The Villages
HARD
90 mins
Dynamic Programming
Topics (Covered in this problem)
Problem solved
Badge
Skill meter
Dynamic Programming
-
-
Other topics
Problem solved
Badge
Skill meter
Strings
-
-
Matrices (2D Arrays)
-
-
Linked List
-
-
Sorting
-
-
Binary Search
-
-
Stacks & Queues
-
-
Trees
-
-
Graph
-
-
Greedy
-
-
Tries
-
-
Arrays
-
-
SQL
-
-
Binary Search Trees
-
-
Heap
-
-
Bit Manipulation
-
-
Solve problems & track your progress
Checkout your overall progress in every topic here
Become
userLevel
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.

Connect The Villages

Contributed by
Akhilesh Singh Bhadauria
Hard
yellow-spark
0/120
Avg time to solve 90 mins
Success Rate 30 %
Share
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 )
Sample Input 1 :
2
4
1 2 2
1 3 3
2 4 3
1
3 4 1
3
1 2 4
2 3 5
2
1 3 2
1 2 5
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 :
2
7
1 2 3
1 3 3
3 4 2
3 5 3
4 6 4
5 7 5
4
1 4 2
4 7 10
6 7 1
1 5 12
4
1 2 1
2 3 1
3 4 1
5
1 2 1
1 3 2
2 3 5
3 1 1
3 4 2  
Sample Output 2 :
YES NO YES NO
NO NO NO NO NO
Reset Code
Full screen
Auto
copy-code
Console