PROBLEM LINK:
Author: Hasan Jaddouh
Testers: Kevin Atienza, Sergey Kulik and Vasya Antoniuk
Translators: Vasya Antoniuk (Russian), Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza
DIFFICULTY:
Medium-hard
PREREQUISITES:
Lowest common ancestor, jump pointers, Fenwick tree, binary search
PROBLEM:
Given a tree with N nodes. There are K gangs, and each gang operates on some subset of the nodes. There are Q queries. In each query, you are given some node v and a subset of the gangs S. A node is controlled if it lies in the path between some two nodes that are operated by some gangs in S. What is the nearest distance from V to some controlled node?
QUICK EXPLANATION:
Let G_i be the set of nodes of the i th gang.
Root the tree at node 1, and preprocess the tree so that you can compute the LCA between any two nodes. Also, precompute the depth of every node. Note that the distance between two nodes a and b is \operatorname{depth}(a) + \operatorname{depth}(b) -2\operatorname{depth}(LCA(a,b)).
Let T be a set of nodes. Define C(T) as the set of nodes that are in some path between pairs of nodes in T. Also, for a node v, let D_v(T) be the nearest distance from v to C(T).
The answer to a query (v,S) is then the minimum of the following values:
- \min_{i \in S} D_v(G_i)
- D_v(\{LCA(G_i) : i \in S \})
To compute D_v(T), first compute l = LCA(T). If LCA(l,v) \not= l, then the answer is the distance between v and l. Otherwise, we will perform binary search. Call a node good if one of its descendants is in T. Then the answer is the distance between v and the lowest good ancestor of v. We can find this node quickly using jump pointers.
To quickly determine whether a node is good, we preorder the tree, and set up a Fenwick tree on top of the preorder array, where the value is 1 for node in T,and 0 for nodes not in T. Now, a node is good if the sum of its descendants is positive. Since its descendants form a contiguous subarray in the preorder, this amounts to a range sum query.
Finally, this can still be slow when there is a large gang and this gang is used in many queries. In this case, we compute the values above by gang instead of by query, and then takObserve that the constraint “for every two nodes with the same color, all nodes in the path between them also have the same color” is equivalent to the following:e the minimum at the end.
EXPLANATION:
Controlled nodes
The definition of controlled nodes implies that if you take all the controlled nodes of some gang, then every pair of them is connected by a path that passes only through other controlled nodes. In other words, the set of controlled nodes of a graph induces a subtree of the tree!
We can visualize this in another way by rooting the tree at some node, say, node 1. In this case, if you view only the controlled nodes of some gang, then they also look like a rooted tree, rooted at some node. Their “root” is actually the lowest common ancestor (LCA) of all the controlled nodes of that gang.
More formally, for any set of nodes T, C(T) forms a subtree of the original tree.
Nearest node in a subtree of nodes
One of the subproblems we need to answer is the following: Given a node v and some set of nodes T, find the nearest distance from v to any node in C(T). Let’s denote this by D_v(T). Thus, the answer for a single query with node v and gangs G_{i_1}, G_{i_2}, \ldots, G_{i_t} is D_v(G_{i_1} \cup G_{i_2} \cup \ldots \cup G_{i_t}). So we want to find a way to compute D_v(T).
If we root the tree at node 1, then there are essentially two kinds of positions v can be in, relative to C(T): Either v is a descendant of some node in C(T) or not. We handle these separately:
-
If v is not a descendant of any node in C(T), then the nearest node from v to C(T) must be the root of C(T). To determine this quickly, notice that the root of C(T) is just the LCA of all the nodes in T, and by precomputing the depth (distance from root) of all nodes, we can compute the distance between any two nodes a and b in O(1) time as \operatorname{depth}(a) + \operatorname{depth}(b) - 2\operatorname{depth}(LCA(a,b)).
-
If v is a descendant of some node in C(T), then the nearest node from v to C(T) is the lowest (i.e., the one with the highest depth) ancestor of v that has a descendant in T. To find this node, we can use binary search. To do this quickly, though, we need to have two things.
First, we must have a way to “binary search” among all ancestors of v. Thankfully, jump pointers can help us here. Jump pointers are pointers to ancestors of v at power-of-two heights. To use these pointers, we simply try the largest pointer first. If the node doesn’t satisfy our binary search condition, we move to that node. Otherwise, we stay. Then we use the next pointer. And so on. The following pseudocode illustrates it:
def binary_search_ancestors(v): if good(v): return v for k = 20..0 by -1: if not good(jump[v][k]): v = jump[v][k] return parent[v]Note that jump pointers are also useful for computing LCAs quickly, so this comes at no additional cost.
Next, we need to have a fast way to check whether a node has a descendant in T. We can do this by preprocessing on T. First, we can perform a preorder traversal of the whole tree. Then, we create a binary array with N nodes, where the i th value is 1 if and only if the i th node in the preorder traversal is in T.
So how will this help us? Note that the list of descendants of a node can be found in consecutive positions in the preorder array. This means that, to check whether a node v has a descendant in T, simply check the contiguous subarray corresponding to v has any 1 s. But this is a typical range sum query, which can be quickly solved, for example, using Fenwick trees!
So how fast does this run? Well, the computation of depth, jump pointers, preorder traversal, and the creation of the Fenwick tree can just be done once at the beginning (in O(N \log N) time), and after that,
- If v is not a descendant of any node in T, then the only slow part is computing the LCA of |T| nodes. whole step can be done in O(|T| \log N) time.
- If v is a descendant of some node in T, then the whole process takes O(|T| \log N + \log^2 N) time. The first O(|T| \log N) is from preparing the Fenwick tree, and cleaning up of it, and O(\log^2 N) is from binary search, where each step performs a query to the Fenwick tree.
The worst case to compute D_v(T) therefore is O(|T| \log N)!
Nearest node in an alliance
Unfortunately, we can’t simply use that algorithm to answer every query, because the sum of |G_{i_1}| + |G_{i_2}| + \ldots + |G_{i_t}| across all queries can be very large! We need a couple of observations to speed up the query.
The first observation is that C(G_{i_1} \cup G_{i_2} \cup \ldots \cup G_{i_t}) is actually the union of the following trees:
- C(G_{i_1}), C(G_{i_2}), \ldots, C(G_{i_t})
- C(\{LCA(G_{i_1}), LCA(G_{i_1}), \ldots, LCA(G_{i_t})\})
Here’s an example:
In this image, the numbered nodes are nodes where that gang number operates. (In this example, at most one gang operates in each node.) The left hand side illustrates the controlled nodes across the alliance, i.e., C(G_1 \cup G_2 \cup G_3. In the right, the first three denotes the controlled nodes of each gang individually, i.e. C(G_1), C(G_2), and C(G_3), and the last one denotes the controlled nodes of the LCAs of the gangs, i.e., C(\{LCA(G_1), LCA(G_2), LCA(G_3)\}). You can see that combining all the right ones will result in the left one.
Therefore, D_v(G_{i_1} \cup G_{i_2} \cup \ldots \cup G_{i_t}) must be the minimum among the following values:
- D_v(G_{i_1}), D_v(G_{i_2}), \ldots, D_v(G_{i_t})
- D_v(\{LCA(G_{i_1}), LCA(G_{i_1}), \ldots, LCA(G_{i_t})\})
The last one can be computed in O(|t| \log N + \log^2 N) time (assuming we precompute the LCAs of all gangs beforehand), which is acceptable because the sum of the |t| across all queries is limited. However, computing the first t values is the slow part. This is particularly slow if, for example, there is a really large gang G_i and this gang is used is a lot of queries. The slow parts are the preparation and cleanup of the Fenwick tree for each gang.
Thankfully, we can speed it up by computing D_v(G_i) by gang, not by query. To explain this, note that the naĂŻve algorithm does something like this:
// here, gangs_by_query[j] denotes the gang IDs for the j'th query,
// and v[j] denotes the "v" node of the j'th query, i.e., the capitol.
// answer[j] will contain the final answer for the j'th query.
// loop across all queries
for j=1..Q:
// loop across all gangs in the j'th query
for i in gangs_by_query[j]:
(set up the Fenwick tree for G_i)
(perform binary search across ancestors of v[j])
(clean up the Fenwick tree for G_i)
But if we do it by gang, then it will look like the following:
// compute queries_by_gang
// here, queries_by_gang is a list of lists, all initially empty.
for j=1..Q:
for i in gangs_by_query[j]:
(append j to queries_by_gang[i])
// loop across all gangs
for i=1..K:
(set up the Fenwick tree for G_i)
for j in queries_by_gang[i]:
(perform binary search across ancestors of v[j])
(clean up the Fenwick tree for G_i)
The original version is slow because we need to set up the Fenwick tree for each gang every time it’s used. But if we do it by gang like in the second, we only set up the Fenwick tree for each gang once!
This version now runs in O(K \log N + (Q + \sum t) \log^2 N), which is acceptable.
Time Complexity:
O(N \log N + K \log N + (Q + \sum t) \log^2 N)