COCI '14 Contest 4 #4 Mravi

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.6s
Memory limit: 32M

Problem type

Little Bobi gets up every morning and feeds his favourite pets: ants. He keeps them in a terrarium with a pipe system that can be represented as a tree with N nodes. The pipes are represented by the edges of the tree. The root of the tree is located at node denoted with 1. Inside the pipe system, the liquid flows from a node to its children because of gravity.

We know the flow X_i of each pipe: the percent of fluid from the parent node that flows through that pipe to the child node. Let's observe the following example:

Node 1 from the image has 12 liters of liquid in it and has two pipes after it. One has the flow of X_i = 30, and the other X_i = 70. Node 2 is going to get 3.6 liters and node 3 gets 8.4 liters. In the input data, the sum of flows of pipes going from the same node will always be equal to 100.

Some of Bobi's pipes aren't just regular pipes; they are a bit strange. They are super pipes that have the superpower to square the amount of liquid flowing through them. In the previous example, if the first pipe has the superpower, node 2 gets 12.96 liters and node 3 still gets only 8.4 liters. Notice now that a node has more liquid leaving it than the amount entering it. This is exactly the reason why these pipes are super pipes!

All super pipes can have their superpower turned on or off by Bobi.

The ants live only in the leaves of the tree (nodes that don't have any children). For each leaf, we know the required amount of liquid K_i to feed all ants living in that leaf. Bobi wants to feed his ants by pouring L liters of liquid into the root of the tree. He doesn't have much money so he wants to know the minimum amount of liters of liquid he needs to buy to keep all of his ants fed.

Please note: The input data is such that the required number L will not exceed 2 \cdot 10^9.


The first line of input contains the integer N (1 \le N \le 1000).

Each of the following N-1 lines contain four integers A_i, B_i, X_i, T_i (1 \le A_i, B_i \le N, 1 \le X_i \le 100, 0 \le T_i \le 1) where A_i and B_i are the ends of a pipe (the labels of nodes connected by the pipe), X_i is the flow of the liquid through the pipe, and T_i denotes whether the pipe has a superpower. If T_i is 1, that pipe has a superpower, otherwise it does not.

The following line contains N integers K_i describing the amount of liquid needed for the ants in the i^{th} node. If the i^{th} node is not a leaf, K_i will be -1, otherwise it will be an integer from the interval [1, 10].


The first and only line of output must contain the required number from the task.

Please note: The allowed absolute error from the correct (precise) solution is 0.001.

Sample Input 1

1 2 50 0
1 3 50 0
2 4 25 0
2 5 75 1
-1 -1 4 1 9

Sample Output 1


Explanation for Sample Output 1

If Bobi pours 8 liters of liquid into the root of the tree, node 3 will get 4 liters, node 4 will get 1 liter and node 5 will get 9 liters. These nodes are leaves (they have ants in them) and this is the exact minimum amount the ants need to get. Also, 8 liters is the minimum amount of liquid that satisfies the "ant" conditions.

Sample Input 2

1 2 20 1
1 3 80 1
-1 4 8

Sample Output 2


Sample Input 3

1 2 100 1
2 3 20 0
2 4 20 0
2 5 60 0
4 6 100 1
-1 -1 1 -1 1 2

Sample Output 3



There are no comments at the moment.