P3379 [Template] Lowest Common Ancestor (LCA)

As stated, given a rooted multi-branch tree, find the lowest common ancestor of the specified two nodes.

The first line contains three positive integers $N,M,S$, which denote the number of nodes in the tree, the number of queries, and the index of the root node, respectively. Each of the next $N-1$ lines contains two positive integers $x, y$, indicating that there is a directly connected edge between node $x$ and node $y$ (the testdata guarantees the edges form a tree). Each of the next $M$ lines contains two positive integers $a, b$, asking for the lowest common ancestor of node $a$ and node $b$.

Output $M$ lines, each containing one positive integer, which are the answers to the queries in order.

Constraints: - For $30\%$ of the testdata, $N\leq 10$, $M\leq 10$. - For $70\%$ of the testdata, $N\leq 10000$, $M\leq 10000$. - For $100\%$ of the testdata, $1 \leq N,M\leq 5\times10^5$, $1 \leq x, y,a ,b \leq N$, and it is not guaranteed that $a \neq b$. Sample explanation: The tree structure is as follows:  - First query: the lowest common ancestor of $2, 4$ is $4$. - Second query: the lowest common ancestor of $3, 2$ is $4$. - Third query: the lowest common ancestor of $3, 5$ is $1$. - Fourth query: the lowest common ancestor of $1, 2$ is $4$. - Fifth query: the lowest common ancestor of $4, 5$ is $4$. Therefore, the outputs are $4, 4, 1, 4, 4$ in order. 2021/10/4 testdata update @fstqwq: Added two more sets of testdata to block brute-force jumping. Translated by ChatGPT 5