307490: CF1363E. Tree Shuffling
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Tree Shuffling
题意翻译
给定 $n$ 个节点标号为 $1$ 到 $n$ 的树,且 $1$ 为树根,每个节点上有三个数字 $a_i,b_i,c_i$。$a_i$ 表示修改代价,$b_i,c_i$ 的值为 $0$ 或 $1$ , $b_i$为初始值,$c_i$为目标值。每次可以选择以节点 $u$ 为根节点的子树,去把该子树的所有结点从初始值修改成目标值。修改方法为:可以选择该子树中任意 $k$ ( $k$ 小于等于子树节点的个数)个节点进行交换初始值,使之与该节点的目标值相等,代价为 $k*a_u$。请以最小的代价,把所有点从初始值变成目标值。如果无法修改成功,则输出-1。题目描述
Ashish has a tree consisting of $ n $ nodes numbered $ 1 $ to $ n $ rooted at node $ 1 $ . The $ i $ -th node in the tree has a cost $ a_i $ , and binary digit $ b_i $ is written in it. He wants to have binary digit $ c_i $ written in the $ i $ -th node in the end. To achieve this, he can perform the following operation any number of times: - Select any $ k $ nodes from the subtree of any node $ u $ , and shuffle the digits in these nodes as he wishes, incurring a cost of $ k \cdot a_u $ . Here, he can choose $ k $ ranging from $ 1 $ to the size of the subtree of $ u $ . He wants to perform the operations in such a way that every node finally has the digit corresponding to its target. Help him find the minimum total cost he needs to spend so that after all the operations, every node $ u $ has digit $ c_u $ written in it, or determine that it is impossible.输入输出格式
输入格式
First line contains a single integer $ n $ $ (1 \le n \le 2 \cdot 10^5) $ denoting the number of nodes in the tree. $ i $ -th line of the next $ n $ lines contains 3 space-separated integers $ a_i $ , $ b_i $ , $ c_i $ $ (1 \leq a_i \leq 10^9, 0 \leq b_i, c_i \leq 1) $ — the cost of the $ i $ -th node, its initial digit and its goal digit. Each of the next $ n - 1 $ lines contain two integers $ u $ , $ v $ $ (1 \leq u, v \leq n, \text{ } u \ne v) $ , meaning that there is an edge between nodes $ u $ and $ v $ in the tree.
输出格式
Print the minimum total cost to make every node reach its target digit, and $ -1 $ if it is impossible.
输入输出样例
输入样例 #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
输出样例 #1
4
输入样例 #2
5
10000 0 1
2000 1 0
300 0 1
40 0 0
1 1 0
1 2
2 3
2 4
1 5
输出样例 #2
24000
输入样例 #3
2
109 0 1
205 0 1
1 2
输出样例 #3
-1