Ants Colony

Time limit2sMemory limit128 MB

Summary

Build a weighted tree where each new node attaches to an earlier one, then answer distance queries between pairs of nodes.

Level: Medium6 of 10
Topics: Tree, DFS, Prefix sum, Graph
Solved: No attempts yet

Problem

A colony of ants is proud of the magnificent, sprawling home they have built. But its sheer size has become a problem: many ants do not know how to travel between different parts of the colony. They urgently need your help.

The colony consists of $N$ anthills connected by tunnels. Being meticulous, the ants numbered the anthills in the order they were built. The first anthill, numbered $0$ , needed no tunnel. For each later anthill, numbered $1$ through $N-1$ , the ants dug exactly one tunnel connecting the new anthill to one of the anthills that already existed. That single tunnel was always enough to let an ant reach any previously built anthill (possibly by passing through others), so the ants never dug extra tunnels and simply kept building.

Given the structure of the colony and a list of queries, compute for each query the length of the shortest path between the two given anthills. The length of a path is the sum of the lengths of all tunnels traveled.

Input

The input consists of several test cases. Each test case is given over several lines.

The first line contains an integer $N$ , the number of anthills in the colony ( $2 \le N \le 10^5$ ).

Each of the next $N-1$ lines describes one tunnel. For $1 \le i \le N-1$ , line $i$ contains two integers $A_i$ and $L_i$ , meaning that anthill $i$ is connected directly to anthill $A_i$ by a tunnel of length $L_i$ ( $0 \le A_i \le i-1$ and $1 \le L_i \le 10^9$ ).

The next line contains an integer $Q$ , the number of queries ( $1 \le Q \le 10^5$ ). Each of the next $Q$ lines contains two distinct integers $S$ and $T$ ( $0 \le S, T \le N-1$ ), the source and target anthills of one query.

The last test case is followed by a line containing a single $0$ .

Output

For each test case, output a single line with $Q$ integers: the length of a shortest path between the anthills of each query, in the same order as the queries appear in the input.

Examples5

Example 1

Input

6
0 8
1 7
1 9
0 3
4 2
4
2 3
5 2
1 4
0 3
2
0 1
2
1 0
0 1
6
0 1000000000
1 1000000000
2 1000000000
3 1000000000
4 1000000000
1
5 0
0

Expected output

16 20 11 17
1 1
5000000000

Example 2
Input
```
2
0 1
2
1 0
0 1
0
```
Expected output
```
1 1
```

Example 3

Input

Expected output

15 35 25

Example 4

Input

Expected output

10 9 3

Example 5

Input

Expected output

15 15 14 7