2
$\begingroup$

I'm working on a problem and I've managed to design an efficient algorithm, but I'm stuck at the last part.

After some processing I'm left with a tree and I have to answer several queries of the form $(x,y)$, such that for each such query we have to print the minimum cost edge on the path from $x$ to $y$.

Now, this can be done by getting the smaller value between the shortest edge on the path from $x$ to $\text{lca}(x, y)$ and the shortest edge on the path from $y$ to $\text{lca}(x, y)$.

My question is, how do we actually get the min-cost edge on the path from say $x$ to $\text{lca}(x, y)$ ? Do we just simply use a breadth first search? And wouldn't that actually beat the purpose of computing the lowest common ancestor?

Improve this question
$\endgroup$
8
  • $\begingroup$ Is the tree a rooted tree, so that each node has a well-defined parent node? $\endgroup$ – Nathan Davis Nov 23 '16 at 21:06
  • $\begingroup$ No, it's just a regular graph (data structure - wise). $\endgroup$ – user43389 Nov 23 '16 at 21:18
  • $\begingroup$ 1. Do you have any upper bounds on the degree of each node? Is it a binary tree (i.e., each node has degree 3)? 2. Do you have any guarantees on how "balanced" the tree is, i.e., that its depth (or diameter) is $O(\log n)$, where $n$ is the number of nodes, or at least is much smaller than $n$? 3. Do you need to handle online queries, or all queries given in advance (i.e., you receive all queries before you need to answer any of them)? $\endgroup$ – D.W.♦ Nov 23 '16 at 22:23
  • $\begingroup$ 4. I realize your tree is unrooted. If dealing with rooted trees is easier, one technique you can always consider (if it's helpful) is to pick any node and treat it as the root, and then apply some algorithm for rooted trees. $\endgroup$ – D.W.♦ Nov 23 '16 at 22:25
  • $\begingroup$ 5. If there are a total of $n$ nodes, I suspect I can find an algorithm that answers each such query in $O(\log n)$ time, after a preprocessing step that takes $O(n \log n)$ time and uses $O(n \log n)$ space for the extra data computed by preprocessing. Is that useful? Should I write that up? This is better than breadth-first search, which takes $O(n)$ time to answer each query, but might not be optimal. I don't know if there's an algorithm that can answer such queries in $O(1)$ time, after a $O(n)$-time $O(n)$-space preprocessing step (like for LCAs). $\endgroup$ – D.W.♦ Nov 23 '16 at 22:38

Your Answer

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

Browse other questions tagged or ask your own question.