Вам дано дерево с
N вершинами. Здесь дерево - это разновидность графа, а точнее, связный неориентированный граф с
N−1 ребром, где
N - количество его вершин.
I-е ребро (
\(1<=i<=N-1\)) соединяет вершины
ai и
bi и имеет длину
ci.
Вам также дано
Q запросов и целое число
K. Для каждого
j-го запроса (
\(1<=j<=Q\)) найдите длину кратчайшего пути от вершины
xj к вершине
yj через вершину
K.
Входные данные
В первой строке записано целое число
N (
\(3<=N<=10^5\)). В следующих
N строках записаны вершины
ai и
bi (
\(1<=a_i,b_i<=N\),
\(1<=i<=N-1\)) и длина между ними
ci (
\(1<=c_i<=10^9\),
\(1<=i<=N-1\))
Далее идут два числа
Q и
K (
\(1<=Q<=10^5\),
\(1<=K<=N\)). В последних
Q строках записаны целые числа
xj,
yj (
\(x_j \neq y_j\),
\(x_j \neq K\),
\(y_j \neq K\) \(1<=j<=Q\), )
.
Заданный граф является деревом.
Выходные данные
Выведите ответы на запросы в
Q строках. В
j-й строке выведите ответ на
j-й запрос.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5 |
3
2
4 |
Кратчайшие пути для трех запросов следующие:
Запрос 1: Вершина 2 → Вершина 1 → Вершина 2 → Вершина 4: Длина 1 + 1 + 1 = 3
Запрос 2: Вершина 2 → Вершина 1 → Вершина 3: Длина 1 + 1 = 2
Запрос 3: Вершина 4 → Вершина 2 → Вершина 1 → Вершина 3 → Вершина 5: Длина 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 |
Путь для каждого запроса должен проходить через вершину 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 |
|