Distance query - MarisaOJ: Marisa Online Judge

Distance query

Time limit: 1000 ms
Memory limit: 256 MB
You are given a weighted tree of $n$ vertices rooted at $1$. There are $q$ queries, each of the form $(u, v)$, find the shortest distance between $u$ and $v$. ### Input - The first line contain 2 integers $n, q$. - The next $n - 1$ lines, each line contains 3 integers $u, v, w$, there is an edge of weight $w$ 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$. - $1 \le w \le 10^9$. ### Example Input: ``` 7 3 1 2 1 1 3 2 2 4 3 2 5 2 3 6 1 3 7 3 4 5 4 6 2 7 ``` Output: ``` 5 7 6 ```