Дано дерево\(^{\text{∗}}\) с \(n\) вершинами и значениями \(l_i, r_i\) для каждой вершины. Вы можете выбрать начальные значения \(a_i\), удовлетворяющие условию \(l_i\le a_i\le r_i\) для \(i\)-й вершины. Дерево считается сбалансированным, если все значения в вершинах равны, а значение сбалансированного дерева определяется как значение любой вершины.
За одну операцию вы можете выбрать две вершины \(u\) и \(v\) и увеличить значения всех вершин в поддереве\(^{\text{†}}\) вершины \(v\) на \(1\), рассматривая \(u\) как корень всего дерева. Обратите внимание, что \(u\) может быть равен \(v\).
Ваша цель — выполнить последовательность операций так, чтобы дерево стало сбалансированным. Найдите минимально возможное значение дерева после выполнения этих операций. Обратите внимание, что вам не нужно минимизировать количество операций.
Выходные данные
Для каждого набора данных выведите одно целое число — минимально возможное значение, к которому могут быть приведены все \(a_i\) после выполнения операций. Можно доказать, что ответ всегда существует.
Примечание
В первом наборе данных вы можете выбрать \(a=[6,6,0,5]\).
Вы можете выполнить следующие операции, чтобы сделать все \(a_i\) равными:
- Выберите \(u=4\), \(v=3\) и выполните операцию \(5\) раз.
- Выберите \(u=1\), \(v=3\) и выполните операцию \(6\) раз.
Полный процесс показан ниже (числа в скобках — значения \(a\)):
Можно доказать, что это оптимальное решение.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
4
0 11
6 6
0 0
5 5
2 1
3 1
4 3
7
1 1
0 5
0 5
2 2
2 2
2 2
2 2
1 2
1 3
2 4
2 5
3 6
3 7
4
1 1
1 1
1 1
0 0
1 4
2 4
3 4
7
0 20
0 20
0 20
0 20
3 3
4 4
5 5
1 2
1 3
1 4
2 5
3 6
4 7
5
1000000000 1000000000
0 0
1000000000 1000000000
0 0
1000000000 1000000000
3 2
2 1
1 4
4 5
6
21 88
57 81
98 99
61 76
15 50
23 67
2 1
3 2
4 3
5 3
6 4
|
11
3
3
5
3000000000
98
|