Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Given a Tree and pointers to two of it's nodes A and B (a key value of each node is positive).

Find an algorithm that sums up all the values on the path between A and B, when preproccessing is allowed.

share|improve this question

closed as unclear what you're asking by D.W., Luke Mathieson, Juho, Kaveh, Wandering Logic May 19 at 19:28

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

1  
What have you tried? Where did you get stuck? We want to help you with your specific problems, not just do your work. However, as it is we don't know what this problem is and thus how to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? –  D.W. May 19 at 6:18

1 Answer 1

up vote 8 down vote accepted

Preproccessing: $O(n)$

For each node in the tree, we will keep the sum of all the values on the path from the root to the node.

Additionally, we will prepare for LCA (lowest common ancestor) queries in $O(n)$ time.

Query: $O(1)$

When asking for the sum on the path $A \rightarrow B$, Return $$\text{sumFromRoot}(A) + \text{sumFromRoot}(B) - 2 \cdot \text{sumFromRoot}(\text{LCA(A,B)})$$

We subtract twice the path from the LCA to the root, as we counted it twice in the sums from the root.

share|improve this answer

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