We have a tree with n vertices, where vertex 1 is the root. There are q queries, and each query consists of a list of k vertices: u1,u2,…,uk. The goal is to choose two vertices from each query in such a way that their Lowest Common Ancestor (LCA) is as close to the root as possible.
Input:
8 7
1 2
2 3
1 4
2 5
4 6
5 7
7 8
5 4 5 2 2 6
3 2 2 3
6 6 2 5 3 2 2
3 4 3 3
5 6 3 8 7 2
4 2 1 8 5
2 5 2
Output:
2 6
2 3
2 6
3 4
2 6
1 8
2 5
Subtree queries | |
Subtree update | |
Ancestor | |
Shallow | |
Remove subtree | |
Queries on tree | |
Queries on tree 2 | |
Library | |
Black vertices |