354. Distance Between Two Nodes
Print the number of edges on the shortest path between the node holding a
and the node holding b.
In a tree there is exactly one path between any two nodes, so "shortest" is not really a choice: that path must go up from each node to their lowest common ancestor and back down.
That gives the formula directly. If d(x) is a node's depth, the distance is
d(a) + d(b) - 2 * d(lca(a, b))
The doubled term is because the stretch from the root down to the meeting point is counted once in each depth and belongs in neither.
A node's distance to itself is 0, since the meeting point is the node itself.
Constraints - `1 ≤ n ≤ 100000` - `-1000000000 ≤ value ≤ 1000000000` - All values are distinct, and both `a` and `b` appear in the tree. - The input always forms a valid tree rooted at node 1.
Input
The first line contains three integers n, a and b.
The second line contains n values, where node i holds the ith value.
Each of the next n lines contains the left and right child of node i,
using 0 for no child. Node 1 is the root.
Output
Print one integer, the number of edges between the two nodes.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.