Problems
Tree
Tree
A weighted tree is given. Find the distance between two specified vertices.
\InputFile
The first line contains the number of nodes $n~(1 \le n \le 150000)$ in the tree. Nodes are numbered from $0$ to $n - 1$. Each of the following $n - 1$ lines consists of three integers $u, v, w$ representing an edge with weight $w~(0 \le w \le 1000)$, connecting nodes $u$ and $v$. The next line contains the number of queries $m~(1 \le m \le 75000)$. Each of the next $m$ lines contains two integers --- the numbers of vertices between which the distance needs to be computed.
\OutputFile
For each query print the distance between the nodes with the given numbers.
\includegraphics{https://static.e-olymp.com/content/30/30e21658a34af2dea3188894b35a13d48aaf95c0.gif}
Input example #1
3 1 0 1 2 0 1 3 0 1 0 2 1 2
Output example #1
1 1 2