Задача: Транзитный путь
Вам дано дерево с 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 |
|
Ваш ответ: