Last Updated: 1 Jul, 2021
Ninja Land
Ninja
Asked in companies
In Ninja land, there are N cities that are connected to each other by undirected roads. The cities along with all the roads form a tree-like structure. Each city has an initial height associated with it. The heights of the cities can change also. Now Ninja got bored at home and decided to visit different cities. But Ninja only wants to visit two cities if the path between them forms an alternate series of ups and downs. Since Ninja doesn’t know whether the path between the two cities is alternating or not, he asked you to help him.
For Example:
Suppose Ninja is currently standing at X city and want to visit Y city. Let the heights of all the cities in the path from X to Y(including X and Y) are 10 20 5 30. Now these series of heights forms and alternate series. So Ninja will visit the city Y.
Some examples of alternate series are 15 4 11 8 25, 100 120 50 70 60 but the series like 3 5 4 1, 6 3 10 12 are not alternating.
Now you will be asked q queries, and there are two types of queries:
1 X Y: change the height of city X to Y.
2 X Y: Check whether the path between city X to Y is alternating or not.
Input Format:
The first line contains two space-separated integers ‘N’ and ‘Q’ denoting the number of cities in the Ninja Land and the number of queries.
The next N-1 lines will contain two space-separated integers X and Y, denoting that there is an undirected edge between city X and city Y.
The next line contains ‘N’ space-separated integers denoting the initial heights of each city.
The next q lines contain three space-separated integers representing the queries of both types.
Output Format:
Output for each query of type two only, whether the path between the two cities of that query is alternating or not.
Output for each query will be printed in a separate line.
Note
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints:
1 <= N,Q <= 10^5
1 <= X,Y <= N
1 <= height[i] <= 10^9
Where N is the number of cities, Q is the number of queries, X and Y represent the cities, and height[i] represents the height of the i’th city.
Time Limit: 1 sec.
Approaches
We will use heavy-light decomposition to solve this problem. The idea of this algorithm is that we will try to break the given tree into some segments where we can apply the segment tree to process each query in logarithmic time.
More about this algorithm can be found at the given link:
https://cp-algorithms.com/graph/hld.html
Algorithm:
- dfs_size function:
- It will calculate the subtree size, depth, parent, and child with the maximum subtree size of each node.
- dfs_labels function:
- It will calculate a new array of the given heights and the position of each node in the new array so that we can apply a segment tree to this newly created array.
- dfs_chain function:
- It will calculate an array that contains the information about the segment each node belongs to.
- lca_int function:
- It will calculate the ancestors in the power of 2 of each node which will be used during calculating Lowest Common Ancestors.
- getLca function:
- It will calculate the Lowest Common Ancestors of two nodes.
- merge function:
- It merges two segments of the segment tree.
- build function:
- It will build the segment tree.
- The segment tree will store the following information of each segment:
- Length of the segment.
- Whether the segment is alternating or not.
- The leftmost element, second leftmost element, rightmost element, second rightmost element of each segment.
- update function:
- It will update the segment tree when applying the first type of query.
- query function:
- It returns the segment between two given cities.
- merge2 function:
- It merges two segments when the segments are present in reverse order.
- given function:
- Represent the tree in adjacency array.
- Call the above functions for pre-processing.
- Iterate over all the queries.
- If it is of the first type, update the segment tree.
- Else first calculate the LCA. Then check the path from city X to LCA and then from city Y to LCA, and finally merge these two segments.
- If the resulting segment is alternating, print ‘YES’ else ‘NO’.
Similar problems