Close
Topic list
Connect The Villages
HARD
90 mins
Dynamic Programming
Topics (Covered in this problem)
Problem solved
Skill meter
Dynamic Programming
-
-
Other topics
Problem solved
Skill meter
Strings
-
-
Matrices (2D Arrays)
-
-
-
-
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
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
Hard
0/120
Avg time to solve 90 mins
Success Rate 30 %
Share

## Problem Statement

#### Each question is of the following format :

``````U V W
``````

#### 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
``````
Auto
Console