PROBLEM LINK:
Author: Misha Chorniy
Tester: Lewin Gan
Editorialist: Adarsh Kumar
DIFFICULTY:
Hard
PREREQUISITES:
Square root decomposition, Compressed super-node tree
PROBLEM:
You are given a tree T with N nodes, where each node i has value C[i] initially. You need to process Q queries which can be of two types. For type 1 query, you are asked to add W to value of each node on path between U and V (inclusive). For type 2 query, you need to report smallest value of node on path between U and V (inclusive) whose value is \ge X.
EXPLANATION:
This problem requires you to efficiently query/update on different paths of trees. We can use Compressed super-node tree for this purpose. Basically, this representation of tree will allow us to extend the square-root decomposition solution to tree.
In a linear version each query or update interval [i,j] can be split into three sub-intervals (whenever i and j are not in the same block): the interval [i,a] consisting of all the cells starting at i and ending at the last cell in i’s block, the interval [b,j] consisting of all the cells ending at j and starting at the first cell in j’s block, and the interval [a+1,b-1] which covers a number of full blocks. If i and j are in the same block then all the cells between i and j are queries/updated individually.
After creating a compressed super-node tree, a block will correspond to a supernode’s group. A range query and update will correspond to a query or update on a path in the tree. A query/update path between two nodes i and j will be handled by first finding the lowest common ancestor LCA(i,j). You can refer to this paper for a very well explanation of the same. All that remains is now what information should be stored in each block and how to query/update them.
For each block, keep a global variable which will store how much needs to be added to every node present in this block. For each block, store value of all the nodes present in this block in a multiset for this block. You can update any individual node from this block now in O(logN). Querying values for individual nodes is quite-straight forward after storing all the information. You can also query for the block in O(logN) using multiset. For more implementation details, you can refer to attached solutions.
ALTERNATE SOLUTION:
subtask #1
This subtask can be solved in $O(NlogN)$ with the help of Persistent Segment Tree using the idea which is used in COT. A very well explained article for the solution of COT is already written here( link).If you have any other interesting/simple solution, feel free to discuss them in comments.
Time Complexity:
O(N \sqrt{N} logN)