Connect The Villages

Hard
0/120
Average time to solve is 90m
profile
Contributed by
1 upvote

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, 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 :
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
Hint

Depth First Search

Approaches (2)
Brute Force

Now if you read the problem carefully then if you find out the connection is nothing but a tree as all the villages are connected so to connect all nodes we need at least ‘N’-1 roads and the connected graph with ‘N’ nodes and ‘N’-1 roads is nothing but a tree.

 

Now in a query, we add one road between two villages and remove one road from the tree in such a way that the graph still remains connected means the graph still remains a tree.

 

In the naive approach for each query, We will be provided with two villages let’s say those are ‘u’ and ‘v’ and we have to find out the maximum distance between two adjacent villages which are directly connected by a road with each other and they are on the path when we are going from village ‘v’ to village ‘u’ or vice versa and then we check if the maximum distance we found earlier is greater than the value we have provided with the new road in query than the answer is ‘YES’ else answer is ‘NO’ push appropriate answer in result ‘ans’ and return that array.

The steps are as follows:

dfs(currentVillage, parentVillage, targetVillage, maximumDistance, graph){

  1. If ‘currentVilllage’ is the ‘targetVillage’ then return ‘maximumDistance’.
  2. Intialize a variable ‘returnDistance’ with value as 0.
  3. Else for each node adjacent to the current node if that is not the parent node
    • For the current village only update the ‘maximumDistance’ with the distance between the current village and ‘currentVillage’ and call dfs for the current village and store the result of this call in ‘returnDistance’ if the returned value is greater than ‘returnDistance’.

 

findMaximum(u, v, graph, n):

  1. Here ‘u’ and ‘v’ are the villages in which we want to create a new road.
  2. ‘n’ is the total number of villages and ‘graph’ represents the network of roads or in sort the ‘tree’.
  3. Call dfs() for root ‘u’ and call the parent of ‘u’ as -1 ‘targetVillage’ is ‘v’ ‘maximumDistance‘ as 0 and ‘graph’ is our ‘graph’ we received as the parameter of the current function.
  4. Return the maximum distance path we received from the above function call.

connectVillages(n, road, q, query):

  1. ‘n’ represents the number of villages and ‘q’ represents the number of queries.
  2. ‘road‘ represents the tree structure of the roads between the villages and the distance of the road.
  3. ‘query’ represents the queries of the village associates.
  4. First, create the tree from the ‘road’ named as ‘graph’.
  5. Declare 'ans' array.
  6. Now process all queries:
    • Find the maximum distance as we discussed above in the editorial using findMaximum() function.
    • If the maximum distance is greater than 'w' then the answer is 'YES'.
    • Else the answer is 'NO'.
    • Append the appropriate answer in the ‘ans’ array.
  7. Return ‘ans’
Time Complexity

O( Q*N + N ), Where ‘N’ is the number of Villages and ‘Q’ is the number of queries.

O( N ) is the total time it takes to create the tree.

Each query takes O( ‘N’ ) time and there are ‘Q’ 

Hence the time complexity will be O( Q * N +  N ).

Space Complexity

O( N  ), Where ‘N’ is the number of Villages.

 

All the arrays we created can take at most O( N ) time as there are only ‘N’ nodes.

Hence the space complexity will be O( N ).

Code Solution
(100% EXP penalty)
Connect The Villages
Full screen
Console