Codeforces Round 646 (Div. 2) |
---|
Закончено |
У Ashish есть дерево, состоящее из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$, с корнем в вершине $$$1$$$. $$$i$$$-я вершина дерева имеет стоимость $$$a_i$$$, и в ней записана бинарная цифра $$$b_i$$$. Ashish хочет, чтобы в конце в $$$i$$$-й вершине была записана бинарная цифра $$$c_i$$$.
Для этого, он может выполнить следующую операцию любое количество раз:
Он хочет выполнить операции так, чтобы у каждой вершины в итоге оказалась цифра, соответствующая желаемой цифре для этой вершины.
Помогите ему найти минимальную общую стоимость, за которую можно сделать так, чтобы после проведения всех операций для каждого $$$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$$$.
Название |
---|