This page is still under construction.

Parts of this page are still being built. What you see may change.

LCA and queries

Time limit2sMemory limit512 MB

Summary
For each query with a designated root r, report the LCA of u and v in a tree of up to 100,000 vertices.
Level

Hard8 of 10

Topics
Tree, DFS, Binary search, Implementation
Solved
No attempts yet

Problem

You are given a tree T with N vertices. Write a program that answers the following query.

  • r u v: treating r as the root of T, print the lowest common ancestor (LCA) of u and v.

The vertices are numbered 1 through N. Taking r as the root fixes every ancestor relation relative to r, so the same u and v can give a different answer under a different r. When the root is r, the LCA of u and v is the vertex farthest from r among the vertices that lie on both the path from r to u and the path from r to v.

Input

The first line contains the number of vertices N (1 ≤ N ≤ 100,000). Each of the next N-1 lines contains the edge information u and v (1 ≤ u, v ≤ N) of the tree T. The vertices u and v are the two endpoints of that edge.

The next line contains the number of queries M (1 ≤ M ≤ 100,000). Each of the next M lines contains three integers r, u, v (1 ≤ r, u, v ≤ N) describing one query.

Output

For each query, print the number of the LCA vertex, one per line.

Examples3

  1. Example 1

    Input
    7
1 2
2 3
2 4
1 5
5 6
4 7
5
1 2 7
3 1 5
2 1 7
5 6 2
6 2 3
    Expected output
    2
1
2
5
2

  2. Example 2

    Input
    2
2 1
4
1 1 2
1 2 2
2 1 2
2 2 1
    Expected output
    1
2
2
2

  3. Example 3

    Input
    8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
6
1 8 8
8 1 1
4 1 8
1 4 6
8 2 5
5 3 7
    Expected output
    8
1
4
4
5
5