PROBLEM LINK:
[Practice][111]
[Contest][222]
Author: Pavel Sheftelevich
Tester: Karan Aggarwal
Editorialist: Praveen Dhinwa
DIFFICULTY:
medium hard
PREREQUISITES:
longest common ancestor(lca) of nodes in a tree, subtree sum, heavy light decomposition
PROBLEM:
You are given a tree consisting of n node. Each time, you want to insert a route from node u to v in the tree. Before inserting the route, you want to find the number of already inserted routes which intersect with the current route. Two routes are said to be intersecting with each other, if they have at least one node in common.
QUICK EXPLANATION
Let us suppose we want to insert a route from node u to v. Let lca(u, v) = w. We can categorise the already inserted routes which intersect with this route into one of the below two categories.
- The routes (u', v') s.t. their lca w' is a strict ancestor of w.
- The routes (u', v') s.t. their lca w' lies inside the subtree rooted at w.
We can find number of routes in each of the categories by finding sum of all the nodes in a subtree.
-
The routes (u', v') s.t. their lca w' is a strict ancestor of w. This means that only one of the u' or v' will lie inside the subtree rooted at w. Both can not lie inside as in that case their lca won’t be a strict ancestor of w. Both can’t lie outside as their route won’t intersect with route u, v. For finding this information, let us maintain a value P for each node. We update the array P in the following way. When we add a route from u to v. We add 1 in P[u] and P[v], and subtract 2 from P[w]. While answering a query for route u, v, we can find the routes of category 1 and 2 using P values as follows. We can find count of such u''s or v''s by finding sum of P values of all the nodes in the subtree of w.
-
The routes (u', v') s.t. their lca w' lies inside the subtree rooted at w. In this case, it is necessary that their lca w' will lie in the route (u, v). It means that we can uniquely identify the routes with their lca values. So, finding number of routes in this category will be same as finding number of lca values of previous routes which lie on the route (u, v). Let in_time[i] denote the enter time of dfs for node i and out_time denote the exit time of the dfs. Suppose we want to add +val at some node x, then we can do +val at in_time[x] and - val at out_time[x]. Then the sum sum of path from root to vertex x will be equal to prefix sum of values up to in_time[x]. Using this information, we can find sum of values on a path too
Finding sum of values of all the nodes of subtree can be done by linearising the tree into an array such that the subtree corresponds to a consecutive interval. It can be done by finding pre order of the tree. After that the problem reduces into an array point update and finding sum of elements in some range of the array which can be done using BIT or segment tree.
EXPLANATION:
We want to insert routes one by one and before inserting a route we want to find out number of already inserted routes with which the route we are going to insert intersects with. As a route can contain many nodes, we have to somehow find the small crucial information which can help us identify whether two paths intersects with each other or not.
Find the existence of intersection of two paths
Let us say that (u', v') be an already inserted route. We want to find whether (u, v) route can intersect with it or not. The trivial solution will be to visit over all the nodes in the tree and checking whether those two nodes lie on these two paths or not. One important information which can help is the lowest common ancestor (lca) of the nodes.
Let us learn how lca information can help in this. Let w' denote the lca of (u', v') and w denotes that of u, v. Let us use this information to identify whether a node x lies on a path u, v or not. We can split the path (u, v) into two subpaths (u, w) and (w, v), and check whether the node x lies on any of these paths. Notice that in path (u, w), w is an ancestor of u. So, if x lies on it, then lca(x, u) should be x and lca(x, w) should be w.
Now, let us use this information to solve the problem of checking whether two paths (u', v') and (u, v) intersect or not. There can be two cases.
- w' is a strict ancestor of w. Then, two paths intersect if and only if either u' or v' lie in the subtree of w.
- w' lies inside the subtree rooted at w. In this case, both u' and v' will lie in the subtree of w. Also the two paths will intersect if and only if w' lies on the path u, v.
Now, we have found the two necessary conditions for checking existence of intersections of two routes. We can extend the same logic by finding the appropriate values required to get the number of intersections too. Next section describes that.
Extending to counting version
So, before inserting a (u, v) route, we want to find out number of already routes which intersect with it. We know the two conditions mentioned can not be mutually satisfied. So, if we just find number of routes satisfying condition 1 and 2, then their total will denote total number of intersecting routes.
-
w' is a strict ancestor of w. Then, two paths intersect if and only if either u' or v' lie in the subtree of w.
For finding this information, let us maintain a value P for each node. When we add a route from u to v. We add 1 in P[u] and P[v], and subtract 2 from P[w]. Let S_i denote the sum of values of P for all the nodes in the subtree of i. We can find number of routes of this type as follows. It will be equal to S_i.
Proof: Let us see why.- If both u' and v' lie in the subtree of w, i.e. their then this should not be counted. It is indeed not counted as w' also lies in the subtree and we had added +1 for u', +1 for v', but -2 for 'w, which cumulatively become zero.
- If either u' or v' lies in the subtree of w, but not both. In this case, w' can only be a strict ancestor of w. In that case, we will add +1 for either u or v, i.e. it will be counted only once.
-
w' lies inside the subtree rooted at w. Earlier we noticed that in this case, routes will intersect if and only if w' lies on the path u, v. So, we have to find number of lca’s w' of routes (u', v') such that they lie on the path u, v. For that, let us maintain an array lcaCounts for each node of the graph, such that lcaCounts[i] denotes number of lcas w' such that w' = i. Now, we have to find sum of lcaCounts array on a path. Updating a single value on some node of the tree by 1 and finding the sum of nodes on a path can be found using one of the following approaches.
- Heavy Light Decomposition approach : We can decompose the tree into heavy light paths. On the heavy paths, we can maintain a binary indexed tree which tell the sum of values in a given range. For the heavy nodes, we will use the range query and we can manually calculate the sum over all light nodes as their count is small. You can learn about heavy light decomposion online. Its time complexity will be \mathcal{O}(logn^2). A well written code can only pass the problem time limit.
- Reducing into BIT over flattened tree : Let inTime[i] denote the enter time of dfs for node i and outTime denote the exit time of the dfs. Suppose we want to add +val at some node x, then we can do +val at inTime[x] and - val at outTime[x]. Then the sum sum of path from root to vertex x will be equal to prefix sum of values up to inTime[x]. Using this information, we can find sum of values on a path too.
TIME COMPLEXITY
\mathcal{O}(logn) per query. \mathcal{O}(logn) time will be in finding lca and same will be in querying the BIT.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution
Tester’s solution
[111]: http://www.codechef.com/problems/TRAVTREE
[222]: http://www.codechef.com/LTIME37/problems/TRAVTREE