Lowest common ancestor in a root tree.

[FreeSocks]

Hello guys!

I'm having an issue understanding how to exactly approach the following problem:

Rooted tree is given on the standard input as a List of parents. First line contain the number N of the vertices, labeled from 1 to N, and on each of the next N всхея – the father of the corresponding vertex (I-th of these lines contain the father of the vertex I). As a father of the root of the tree the nonexisting vertex 0 is mentioned. The last line will contain the vertices u and v separated by an interval.

And on the single line of the standard output the program has to print the lowest common ancestor of u and v in the given rooted tree.

I am given the following example input :

  10
0
1
2
3
3
5
5
7
5
2
6 10

And the following example Output :

2

I'm really failing to understand exactly how to approach this problem, so if anyone can give a hint or show me some example so i can get e better idea.
Because i try to get a somewhat of a tree built, but how do you exactly make this search ?

Thanks in advance !

[lucifer21]

a basic approach would be to get the root to u path and root to v path.
Then compare those two paths and the node previous to the first mismatch will be the LCA of u and v.

[FreeSocks]

Dont they have both the same root or I'm not understanding you properly ?

[keskiverto]

From the input data we can trace the ancestry for each node:

6 ->5->3->2->1->0
10->2->1->0

The reverse of those are the paths from 0 to the nodes:

0->1->2->3->5->6
0->1->2->10

You can get from 0 to 6 and 10.
You can get from 1 to 6 and 10.
You can get from 2 to 6 and 10.
After that the paths differ.
The 2 is thus the answer.