LCA - MarisaOJ: Marisa Online Judge

LCA

Time limit: 1000 ms
Memory limit: 256 MB
You are given a tree of $n$ vertices rooted at $1$. There are $q$ queries, each of the form $(u, v)$, find the lowest common ancestor of $u$ and $v$. ### Input - The first line contain 2 integers $n, q$. - The next $n - 1$ lines, each line contains 2 integers $u$ and $v$, there is an edge between $u$ and $v$. - The next $q$ lines, each line contains 2 integers $u, v$, an query. ### Output - Print $q$ integers, the answers to $q$ queries. ### Constraints - $1 \le n, q\le 10^5$. - $1 \le u, v \le n$. ### Example Input: ``` 7 3 1 2 1 3 2 4 2 5 3 6 3 7 4 5 4 6 2 7 ``` Output: ``` 2 1 1 ```