Connect The Villages

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’

The following uses the concept of binary lifting and the lowest common ancestor more about it you can read the Binary Lifting Technique. Please read that article first if you do not know how binary lifting works so first learn that technique.

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 find out 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.
 

Now we want to add one road between villages ‘U’ and ‘V’ so we will remove any road which comes on the path of ‘U’ to ‘V’. Now why is that because we add one road and remove one road so total roads still are ‘N’ - 1 and if we remove some road other than this path’s road then that part of the tree will get disconnected and the ‘U’ and ‘V’ villages will have a cycle one path was previously from ‘U’ to ‘V’ we added one more from the ‘U’ to ‘V’ both of these cases violates the property of the tree. You can learn more about it by drawing the tree and adding one road and removing various roads from it.
 

Now we figured out this much, then we will create a 2-D array that will store its ancestor of it. We will store the ancestor in the following way 1, 2, 4, 8…… we will store another array ‘maxValue’ which will store the longest distance road we encountered while reaching the ‘ith ancestor where is [1, 2, 4….].

Now for each query, we will check the largest distance road we encountered on the road from villages to the there lowest common ancestor. If that road is greater than the new road we are adding then the answer is ‘YES’ else answer is ‘NO’.

The steps are as follows:

dfs(currentVillage, maxValue, parent, graph):

1. For j in the range from [1, 20] we will update all the ancestors of the ‘currentVillage’:
   • Store (1 << (j-1)th) ancestor of current village in 'ancestor' variable.
   • Update parent[currentVillage][j] = parent[ancestor][j-1]
   • Update maxValue[currentVillage][j] = max(maxValue[currentVillage][j-1],maxValue[ancestor][j-1]). It basically means we are storing the longest road we encountered from the current Village to it’s (2^j)th ancestor village.
2. Now for all the neighbors ‘j’ of the ‘currentVillage’:
   • If the current neighbor is already visited then don’t visit it again and move to the next neighbor.
   • Set the depth of the current neighbor as the depth of ‘currntVillage’ + 1.
   • Set the parent of the current neighbor as ‘currentVillage’.
   • Set the ‘maxValue’ of the current neighbor as the distance between ‘currentVillage’ and the neighbor ‘j or we can say we are setting distance for (1<<0)th ancestor’.
   • Call dfs function for the current neighbor with appropriate attributes.

lca(u, v, depth, parent, maxValue):

1. If the depth of ‘u’ is greater than ‘v’ swap ‘u’ and ‘v’.
2. Initialize ‘ans’ with 0.
3. For all the ancestors ‘i’ from range 19 to 0:
   • If depth of parent[v][i] >= depth[u]:
     • Update ‘ans’ with max(ans, maxValue[v][i]).
     • Update v with parent[v][i]
4. If now u==v:
   • Return ‘ans’.
5. For ‘i’ in the range from 19 to 0:
   • If both ‘u’ and ‘v’ does not have same (2^i) parent or ancestor:
     • Update ‘ans’ with max( ans, max(maxValue[u][i], maxValue[v][i])).
     • Update u with parent[u][i].
     • Update v with parent[v][i].
6. Update ‘ans’ with max(ans,max(maxValue[u][0],maxValue[v][0])).
7. Return ‘ans’.

connectVillages(n, road, q, query):

1. Create the tree from the ‘N’-1 roads provided named as ‘graph’.
2. Create ‘depth’ array used to store the depth of nodes.
3. Create ‘parent’ and ‘maxValue’ function to store the ancestors and the maximum distance of road we can encounter till that ancestor.
4. Call the dfs(1, maxValue, parent, graph).
5. Create an array to store the answer as ‘ans’.
6. For all queries q:
   • Find the LCA node maxValue for the current two villages of the query.
   • If maxValue is greater than the given ‘w’ in the query then append ‘YES’ in the ‘ans’ array.
   • Else append ‘NO’ in ‘ans’ array.
7. Return ‘ans’