Lowest Common Ancestor

Description

Luogu p3379

Given a tree with $n$ nodes, calculate the lowest common ancestor of two nodes. There will be $m$ queries.

Input & Output

The first line includes three integers $n,m,s$, means the number of nodes, the number of queries, and the root node.

Then, there are $n-1$ lines each contains two numbers $a,b$, indicating that there is an edge between node $a,b$

The next $m$ lines each contains two numbers $a,b$, you need to output the LCA of these two nodes.

Samples

input #1:

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

output #1:

4
4
1
4
4

Constraints

$1 \leq n,m \leq 500000$, $1 \leq s,a,b \leq n$

Time Limit: 3.0s   |   Memory Limit: 512 MB

Practice Mode

💡 Tip: Press Ctrl + Enter (or ⌘ + Enter on Mac) to submit your code instantly.

C++ Python Submit