# Sum of all nodes from A to B in a Tree [closed]

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.

-

## closed as unclear what you're asking by D.W.♦, Luke Mathieson, Juho, Kaveh, Wandering LogicMay 19 '14 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.

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 '14 at 6:18

## 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.

-