e-olymp
Competitions

ADA University - February 12 - LCA

Tree

A weighted tree is given. You must find the distance between two given nodes.

Input

The first line contains the number of nodes of the tree n (1n150000). The nodes are numbered from 0 to n - 1. Each of the next n - 1 lines contains three integers u, v, w that correspond to an edge with weight w (0w1000), connecting nodes u and v. The next line contains the number of queries m (1m75000). In each of the next m lines there are two integers.

Output

For each query print the distance between the nodes with the given numbers.

Time limit 1 seconds
Memory limit 128 MiB
Input example #1
3
1 0 1
2 0 1
3
0 1
0 2
1 2
Output example #1
1
1
2
Author Dmitry Zhukov
Source 2006 Petrozavodsk Summer Session, Ural SU and Orel STU Contest, August