PROBLEM LINK:
Author:
Tester:
Editorialist: Jingbo Shang, Anudeep
DIFFICULTY:
Medium
PREREQUISITES:
Segment Tree, Depth First Search Order
PROBLEM:
Given a rooted tree (actually incrementally growing by add some new leaves on the current one), count how many unordered node pairs (P, Q) such that the P and Q are both in the subtree rooted at the given node V, and Distance(P, Q) is even. Distance(X, Y) = Number of roads in the unique path from X to Y, if the given road network were bi-directional.
EXPLANATION:
Offline Idea
Although the tree is growing along time, we can first load all operations and construct the final tree we will have. Therefore, we can solve this problem using an offline algorithm by activating the node one by one and maintaining some data structure.
Depth First Search Order
Because the query is about the subtree, it is natural to think about the depth first search (DFS) order of the tree, which could help us keep the nodes of a subtree in a consecutive interval. For example, the following tree’s DFS order is: 1 2 5 7 8 3 4 6, where all subtrees are consecutive intervals.
![alt text][6]Specific Query Solution
Then, considering the specific query problem, it is equivalent to the problem that asking how many nodes are there in the subtree rooted at V and their distance to V has the same parity. That is, if there are A nodes at an even distance from V, then picking any two of them is valid; if there are B nodes at an odd distance from V, the situation is same. Therefore, answer = A * (A - 1) / 2 + B * (B - 1) / 2.
Well, the problem is transformed to count the number of nodes in the subtree rooted at node V have odd/even depth, because same depth lead to same parity. As we already constructed the tree, the depth information is observed. And the subtrees are consecutive in the dfs order. Take the odd depth as an example. When a node with odd depth is activated (i.e. added by the operation), we add 1 on its position in the dfs order. And the range sum query on the dfs order can help us the find out the number B. Similarly, A can be maintained too.
Data Structure Choices
To achieve the efficiency requirement, two segment trees (for odd and even depth separately) could be adopted to do the add/sum queries, such that the overall time complexity leads to O(NlogN), where N is the total number of operations.
AUTHOR’S AND TESTER’S SOLUTIONS:
The links will be fixed soon.
Author’s solution can be found here.
Tester’s solution can be found here.
