Определим эйлеров обход дерева (связного неориентированного графа без циклов) следующим образом: рассмотрим рекурсивный алгоритм поиска в глубину, который обходит вершины дерева и нумерует вершины в том порядке, в котором их посещает, при этом учитывается только первое посещение каждой вершины. Данная функция стартует из вершины с номером \(1\), а затем рекурсивно вызывается от всех вершин, которые соединены ребром с текущей и ещё не посещены, в порядке возрастания номеров вершин. Формально данную функцию можно описать так:
next_id = 1
id = массив длины n, заполненный -1
visited = массив длины n, заполненный false
function dfs(v):
visited[v] = true
id[v] = next_id
next_id += 1
for to по соседям v в порядке возрастания:
if not visited[to]:
dfs(to)
Дано взвешенное дерево, вершины которого пронумеровали в порядке эйлерова обхода целыми числами от \(1\) до \(n\) при помощи алгоритма, описанного выше.
Назовём листом вершину дерева, соединённую ребром ровно с одной другой вершиной. В данном вам дереве вершина \(1\) не является листом. Расстоянием между двумя вершинами дерева назовём сумму весов рёбер на единственном простом пути между ними.
Требуется ответить на \(q\) запросов следующего вида: по заданным числам \(v\), \(l\) и \(r\) сообщить кратчайшее расстояние от вершины \(v\) до одного из листов дерева, имеющего номер от \(l\) до \(r\) (включительно).
Выходные данные
Выведите \(q\) чисел — ответы на запросы в порядке, в котором они заданы во входных данных.
Примечание
В первом примере дерево выглядит так:
В первом запросе ближайший к вершине \(1\) лист имеет номер \(4\). Расстояние до него равно \(3\). Во втором запросе ближайшим к вершине \(5\) листом является вершина с номером \(5\), расстояние до которой равно \(0\). В третьем примере ближайшим к вершине \(4\) листом является вершина с номером \(4\), однако она не попадает в отрезок вершин \([1, 2]\) запроса. Единственным листом с номером, попадающим в отрезок \([1, 2]\) является вершина с номером \(2\), расстояние до которой от вершины \(4\) равно \(13\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
1 10
1 1
3 2
3 3
1 1 5
5 4 5
4 1 2
|
3
0
13
|
|
2
|
5 3
1 1000000000
2 1000000000
1 1000000000
1 1000000000
3 4 5
2 1 5
2 4 5
|
3000000000
1000000000
2000000000
|
|
3
|
11 8
1 7
2 1
1 20
1 2
5 6
6 2
6 3
5 1
9 10
9 11
5 1 11
1 1 4
9 4 8
6 1 4
9 7 11
9 10 11
8 1 11
11 4 5
|
8
8
9
16
9
10
0
34
|