You are given a tree with
N vertices. Here a tree is a kind of graph, more precisely, a connected undirected graph with
N−1 edges, where
N is the number of its vertices.
Ith edge (
\(1<=i<=N-1\)) connects
ai vertices and
bi and is
ci.
You are also given
Q queries and an integer
K. For each
jth query (
\(1<=j<=Q\)) find the length of the shortest path from the top
xj to vertex
yj via vertex
K.
Input
The first line contains an integer
N (
\(3<=N<=10^5\)). The following
N lines contain the vertices
ai and
bi (
\(1<=a_i,b_i<=N\),
\(1<=i<=N-1\) ) and the length between them
ci (
\(1<=c_i<=10^9\ ),
\(1<=i<=N-1\))
Next come two numbers
Q and
K (
\(1<=Q<=10^5\),
\(1<=K<=N\)). The last
Q lines contain integers
xj,
yj (
\(x_j \neq y_j\),
\(x_j \neq K\), < span class="math-tex">\(y_j \neq K\)
\(1<=j<=Q\), )
.
The given graph is a tree.
Imprint
Print responses to queries in
Q lines. On the
j-th line print the answer to the
j-th query.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
24
23
4 5 |
3
2
4 |
The shortest paths for the three queries are as follows:
Query 1: Vertex 2 → Vertex 1 → Vertex 2 → Vertex 4: Length 1 + 1 + 1 = 3
Query 2: Vertex 2 → Vertex 1 → Vertex 3: Length 1 + 1 = 2
Query 3: Vertex 4 → Vertex 2 → Vertex 1 → Pinnacle 3 → Vertex 5: Length 1 + 1 + 1 + 1 = 4 |
| 2 |
7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7
| 5
14
22 |
The path for each request must pass through node K = 2. |
| 3 |
10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10
| 17000000000 |
|