Equal path - MarisaOJ: Marisa Online Judge

Equal path

Time limit: 1000 ms
Memory limit: 256 MB
You are given a tree of $n$ vertices Let $f(u, v)$ be the shortest distance between $u$ and $v$. You are given $q$ queries, each of the form $(u, v)$, counting the number of vertices $x$ that $$f(u, x) = f(v, x)$$ ### Input - The first line contain 2 integers $n, q$. - The next $n - 1$ lines, each line contains 2 integers $u, 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 1 4 5 6 3 7 ``` Output: ``` 2 1 0 ```