Обратите внимание: время на тест для этой программы 4 сек, в два раза больше чем обычно.
Ограничение по памяти также в два раза выше чем обычно.**
На ферме Джона имеется \(N\) амбаров (\(2 \leq N \leq 2\cdot 10^5\)) пронумерованных
\(1 \dots N\). Имеется \(N-1\) дорог, где каждая дорога соединяет два амбара и от любого амбара
до любого другого можно добраться посредством некоторой последовательности дорог.
В \(j\)-ом амбаре имеется \(h_j\) снопов сена (\(1\le h_j\le 10^9\)).
ФД хочет переместить сено так, чтобы в каждом амбаре было одинаковое количество стогов.
Он может выбрать любую пару амбаров соединённых дорогой и перевезти некоторое целое количество
снопов сена меньшее ли равное количеству снопов в первом амбаре из первого амбара во второй.
Определите последовательность действий ФД, чтобы добиться цели за минимальное количество
действий. Гарантируется, что такая последовательность существует.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит значение \(N.\)
Вторая строка ввода содержит разделённые одиночным пробелами значения \(h_j\)
для \(j = 1 \dots N\).
Каждая из последних \(N-1\) строк ввода содержи два разделённых одиночным пробелами числа
\(u_i \ v_i\), указывающих, что имеется двунаправленная дорога, соединяющая амбары \(u_i\) и
\(v_i\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите минимальное количество действий, за которым следует последовательность этих действий
по одному в строке.
Каждое действие описывается тремя разделёнными одиночными пробелами положительными целыми числами:
амбар-источник, амбар-приёмник, количество снопов сена, перевозимых из источника в приёмник.
Если имеется множество решений, выводите любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 1 4 5
1 2
2 3
2 4
|
3
3 2 1
4 2 2
2 1 1
|