Дано дерево$$$^{\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$$$.
Ваша цель — выполнить последовательность операций так, чтобы дерево стало сбалансированным. Найдите минимально возможное значение дерева после выполнения этих операций. Обратите внимание, что вам не нужно минимизировать количество операций.
$$$^{\text{∗}}$$$Деревом называется связный граф без циклов.
$$$^{\text{†}}$$$Вершина $$$w$$$ принадлежит поддереву вершины $$$v$$$, если любой путь от корня $$$u$$$ до $$$w$$$ проходит через $$$v$$$.
Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — количество входных наборов данных.
Первая строка каждого набора данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — количество вершин в дереве.
Затем следуют $$$n$$$ строк. $$$i$$$-я строка содержит два целых числа $$$l_i,r_i$$$ ($$$0\le l_i \le r_i\le 10^9$$$) — ограничения на значение $$$i$$$-й вершины.
Следующие $$$n-1$$$ строк содержат ребра дерева. $$$i$$$-я строка содержит два целых числа $$$u_i,v_i$$$ ($$$1\le u_i,v_i \le n$$$, $$$u_i \neq v_i$$$) — ребро, соединяющее $$$u_i$$$ и $$$v_i$$$. Гарантируется, что заданные ребра образуют дерево.
Гарантируется, что сумма $$$n$$$ по всем наборам данных не превосходит $$$2\cdot 10^5$$$.
Для каждого набора данных выведите одно целое число — минимально возможное значение, к которому могут быть приведены все $$$a_i$$$ после выполнения операций. Можно доказать, что ответ всегда существует.
640 116 60 05 52 13 14 371 10 50 52 22 22 22 21 21 32 42 53 63 741 11 11 10 01 42 43 470 200 200 200 203 34 45 51 21 31 42 53 64 751000000000 10000000000 01000000000 10000000000 01000000000 10000000003 22 11 44 5621 8857 8198 9961 7615 5023 672 13 24 35 36 4
11 3 3 5 3000000000 98
В первом наборе данных вы можете выбрать $$$a=[6,6,0,5]$$$.
Вы можете выполнить следующие операции, чтобы сделать все $$$a_i$$$ равными:
- Выберите $$$u=4$$$, $$$v=3$$$ и выполните операцию $$$5$$$ раз.
- Выберите $$$u=1$$$, $$$v=3$$$ и выполните операцию $$$6$$$ раз.
Полный процесс показан ниже (числа в скобках — значения $$$a$$$):
Можно доказать, что это оптимальное решение.
