E. Перестановка дерева
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Ashish есть дерево, состоящее из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$, с корнем в вершине $$$1$$$. $$$i$$$-я вершина дерева имеет стоимость $$$a_i$$$, и в ней записана бинарная цифра $$$b_i$$$. Ashish хочет, чтобы в конце в $$$i$$$-й вершине была записана бинарная цифра $$$c_i$$$.

Для этого, он может выполнить следующую операцию любое количество раз:

  • Выберите любые $$$k$$$ вершин из поддерева любой вершины $$$u$$$ и переставьте цифры в этих вершинах так, как пожелаете, за стоимость $$$k \cdot a_u$$$. Здесь он может выбрать $$$k$$$ в диапазоне от $$$1$$$ до размера поддерева $$$u$$$.

Он хочет выполнить операции так, чтобы у каждой вершины в итоге оказалась цифра, соответствующая желаемой цифре для этой вершины.

Помогите ему найти минимальную общую стоимость, за которую можно сделать так, чтобы после проведения всех операций для каждого $$$u$$$ в вершине $$$u$$$ была записана цифра $$$c_u$$$, или определить, что это невозможно.

Входные данные

Первая строка содержит одно целое число $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$, обозначающее количество вершин в дереве.

$$$i$$$-я из следующих $$$n$$$ строк содержит 3 разделенных пробелом целых числа $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ $$$(1 \leq a_i \leq 10^9, 0 \leq b_i, c_i \leq 1)$$$ — стоимость $$$i$$$-й вершины, ее начальная цифра и желаемая цифра.

Каждая из следующих строк $$$n - 1$$$ содержит два целых числа $$$u$$$, $$$v$$$ $$$(1 \leq u, v \leq n, \text{ } u \ne v)$$$, что означает, что между вершинами $$$u$$$ и $$$v$$$ в дереве есть ребро.

Выходные данные

Выведите минимальную общую стоимость, за которую можно сделать так, чтобы в каждой вершине была записана желаемая цифра для этой вершины, или $$$-1$$$, если сделать это невозможно.

Примеры
Входные данные
5
1 0 1
20 1 0
300 0 1
4000 0 0
50000 1 0
1 2
2 3
2 4
1 5
Выходные данные
4
Входные данные
5
10000 0 1
2000 1 0
300 0 1
40 0 0
1 1 0
1 2
2 3
2 4
1 5
Выходные данные
24000
Входные данные
2
109 0 1
205 0 1
1 2
Выходные данные
-1
Примечание

Дерево, соответствующие примерам $$$1$$$ и $$$2$$$:

В примере $$$1$$$ мы можем выбрать вершину $$$1$$$ и $$$k = 4$$$ за стоимость $$$4 \times 1$$$ = $$$4$$$ и выбрать вершины $$${1, 2, 3, 5}$$$, переставить их цифры и получить желаемые цифры в каждой позиции.

В примере $$$2$$$ мы можем выбрать вершину $$$1$$$ и $$$k = 2$$$ за стоимость $$$10000 \times 2$$$, выбрать вершины $$${1, 5}$$$, обменять их цифры, после чего аналогичным образом выбрать вершину $$$2$$$ и $$$k = 2$$$ за стоимость $$$2000 \times 2$$$ и вершины $$${2, 3}$$$, обменять их цифры, чтобы получить нужные цифры в каждой позиции.

В примере $$$3$$$ невозможно получить нужные цифры, потому что среди начальных цифр нет цифры $$$1$$$.