[Solved]: Sum of all nodes from A to B in a Tree

Problem Detail: 

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.

Asked By : Gil

Answered By : NightRa

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/25831