1
$\begingroup$

I solved this problem from codechef: problem link

and now I want to change it a bit. Instead of find out the distance between node $u$ and $v$ I want to answer $k$ queries of the form: find node $u$ to which distance from node $v$ is maximum but I'm not able to see fast enough algorithm for it. I think that heavy light decomposition is still my best option. Do you have any ideas?

Finding node to which distance is maximum in this way is $O(n)$ but the challenge here is that I have to answer to $k$ queries so the total complexity is $O(nk)$. I believe that this can be done in $O((n+k)\log n)$.

$\endgroup$
  • $\begingroup$ If it is indeed a tree, there should be one and only one path between any two nodes. You should be able to run a BFS tree search, keeping track of distances to each node, then simply take the furthest one. $\endgroup$ – ryan Nov 24 '17 at 21:50
  • $\begingroup$ That's equivalent to searching the height of the tree of root $v$. $\endgroup$ – Abdous Kamel Nov 25 '17 at 10:14
  • 2
    $\begingroup$ Karaw, you can always reply to comments on your own questions, in theory. The difficulty you're having here is that you've created two accounts, so the system doesn't know that this question is yours. If you use the "contact" link at the bottom of the page, you can get your two accounts merged, and then you'll be able to interact with comments. $\endgroup$ – David Richerby Nov 25 '17 at 14:03
0
$\begingroup$

Start from any node and find (say, with a BFS) a farthest node from it; call it $u$. Then start from $u$ and find a farthest node from it; call it $v$. Nodes $u$ and $v$ achieve the absolute maximum distance in the tree.

Now with 2 more BFS, find the distances of all nodes from $u$, and the distances of all nodes from $v$. At this point you are ready to answer the queries: for each queried node $z$, the most distant node is either $u$ or $v$, depending on which has the larger distance. This solves your problem in $O(n + k)$ time.

$\endgroup$
0
$\begingroup$

Let's say your $k$ queries are in the following order $\{v_1, v_2, \ldots v_k\}$. For $v_1$, we will have no information so we simply do a DFS and determine the furthest node $u$ and return it. Consider $v_1$ to be the root of this DFS tree. For each of $v_1$'s children $\{u_1, u_2, \ldots\}$ we will also keep track of the deepest node in the subtree rooted at $u_i$. Let's call this $d(v_1, u_i)$. Note that the maximum distance node from $v_1$ is:

$$d(v_1) = \max_i d(v_1, u_i)$$

At this point, it is important to note that for the query $v_2$, we can retain a lot of information from $d(v_1, u_i)$ if the path to the furthest node from $v_2$ includes $v_1$. Let's assume w.l.o.g. that $v_2$ is in the subtree rooted at $u_j$ in the DFS tree of $v_1$. We will again do a DFS for the deepest node in the DFS tree of $v_2$, however when we hit $v_1$ we can stop and we only need to retain the distance $\delta(v_2, v_1)$. Now we compute $d(v_2)$ as:

$$d(v_2) = \max \{ \max_i d(v_2, y_i) , \ \delta(v_2, v_1) + \max_{i \neq j} d(v_1, u_i) \}$$

This idea can be repeated for the rest of the queries where $v_i$ relies on the information from the queries of $\{v_1, v_2, \ldots v_{i-1}\}$. At query $v_i$ we can describe the work as follows. Consider the DFS tree rooted at $v_i$, the "search" work done at any subtree rooted at $\{v_1, v_2, \ldots v_{i-1}\}$ is constant based on our precomputed values. We need only care about the work done before we reach these nodes. Here is an example analysis where we consider the query $v_{i+1}$ is in the "middle" of the largest remaining subtree.

  1. First query takes $cn$ and splits the tree into trees $T_1$ and $T_2$ of size $n/2$ each.
  2. Second query takes $cn/2$ and splits $T_1$ into trees $T_3$ and $T_4$ of size $n/4$ each.
  3. Third query takes $cn/2$ and splits $T_2$ into trees $T_5$ and $T_6$ of size $n/4$ each. At this point we have 4 trees: $\{T_3, T_4, T_5, T_6\}$.
  4. This goes on and on.

If we assume $k = 2^\ell - 1$, then we get the summation:

$$T(n) = \sum_{i = 0}^{\ell-1} 2^i\frac{n}{2^i} = O(\ell \cdot n) = O(n \log k)$$


As a side note, much of the work will depend on the ordering of the queries. For instance if we have a linked list of edges: $\{(v_1, v_2), (v_2, v_3), \ldots\}$ and we assume the query order is $\{v_1, v_2, \ldots v_k\}$ then:

  1. First query takes cn, and splits the tree into trees $T_1$ and $T_2$ of size $1$ and $n-1$ each.
  2. Second query takes c(n-1), and splits $T_2$ into trees $T_3$ and $T_4$ of size $1$ and $n-2$ each.
  3. Third query takes c(n-2), and splits $T_4$ into trees $T_5$ and $T_6$ of size $1$ and $n-3$ each.
  4. This goes on and on.

We get the final complexity is:

$$T(n) = \sum_{i = 0}^k c(n-i) = O(nk)$$

However, if we order the queries as $\{v_k, v_{k-1}, \ldots v_1\}$ then:

  1. First query takes cn, and splits the tree into trees $T_1$ and $T_2$ of size $k-1$ and $n-k + 1$ each.
  2. Second query takes c(k-1), and splits $T_1$ into trees $T_3$ and $T_4$ of size $k-2$ and $1$ each.
  3. Third query takes c(k-2), and splits $T_3$ into trees $T_5$ and $T_6$ of size $k-3$ and $1$ each.
  4. This goes on and on.

We get the final complexity is:

$$T(n) = cn + \sum_{i = 0}^{k-1} c(k-i) = O(n + k^2)$$

Even with an ordering of $\{v_k, v_{k/2}, v_{k/4}, v_{3k/4}, \ldots\}$ we could get a complexity of $O(n + k \log k)$. So the complexity very much depends on the ordering of the queries. If we assume the queries are random then this is still okay and we can get $O(n \log k)$. If we can re-order the queries then we can greedily pick the node that splits the tree closest to in-half and continue. This should give approximately $O(n \log k)$, though I have no proof and will not work through it here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.