National Olympiad in Informatics, China, 2006
Networking has become an essential part of the modern world. Each day, there are hundreds of millions of users that use the web for activities such as education, research, entertainment, and more. However, a point that cannot be ignored is the huge operating costs of networks. So, appropriately charging users of the net is both necessary, and reasonable.
City MY's NS high school has an educational network like such. The number of users in the network is , with users labeled . Between the users, the network consists of routers and cables. The users, routers, and cables form a perfect binary tree structure. Every leaf node in the tree represents a user, every non-leaf node (gray) in the tree represents a router, and every edge represents a network cable (see figure below, where each node is labeled with the number of the user it represents).
The MY networking company's charging scheme is rather special, and is known as "pairwise charging". A fee is charged for all pairs of users . Since each user can independently select from one of two possible payment plans and , the company's charges on the school is related to the choices of each user. This charge is equal to the sum of all pairwise charges between different users.
To make explanations easier, let's first define some terms regarding this network tree:
- Ancestor: The root node has no ancestors. The ancestors of a non-root node include its parent node and the ancestors of its parent node.
- Containment of leaf nodes: Leaf nodes do not contain any leaf nodes. A non-leaf node contains the number of leaf nodes its left child contains, plus the number of leaf nodes its right child contains.
- Distance: Between two nodes in the tree, the distance is the number of edges on the path with the fewest number of edges connecting them.
Regarding any two users and , first find the common ancestor, router , with the smallest distance to each user. Then from the leaf nodes (users) contained by , examine the number of people that have chosen plans and , respectively. We shall call these two numbers and . Next, we follow article X, section Y, clause Z to determine charges (see the following table). Below, is the (already known) data flow between and .
's Payment Plan | 's Payment Plan | Relationship between and | Payment Factor | Actual Charges (Dollars) |
---|---|---|---|---|
Since the final charges is very much related to the payment methods involved, NS high school's users wish to change their own payment plans to minimize the total charge to the school. However, the networking company has already recorded each user's payment plan when they registered. If user wants to change his or her payment plan (from to or from to ), then a fee of dollars must be paid for the company to update their records.
Now the question is, given the initially registered payment plans of every user, as well as , determine how the users can select their own payment plans so that the total fee NS high school pays the network company is as small as possible (plan change charges + pairwise charges).
Input Specification
The 1st line of input contains one positive integer .
The 2nd line contains integers, specifying the payment
plans of user numbers , respectively. Each number
is either a , which indicates that the user's initial plan is , or a
, which indicates that the user's initial plan is .
The 3rd line contains integers, the costs for each user
to update their plan in dollars, respectively .
The next lines contain the data flow table
between pairs of users. The line of input's integer
is the value of .
Output Specification
Your program must output a single integer, representing the minimum amount that NS high school has to pay to the network company in dollars.
Sample Input
2
1 0 1 0
2 2 10 9
10 1 2
2 1
3
Sample Output
8
Explanation
When user number 's payment plan is changed from to , NS high school's network charges will be minimized.
Constraints
In test cases worth of points: ;
In test cases worth of points: ;
In test cases worth of points: , , .
Problem translated to English by .
Comments