Battle of Ryloth

locked

"Droid, is the planet Ryloth one of our targeted worlds?"

"Yes, Emir. Based on resources, accessibility, political influence and overall strategic value, it is currently ranked as number seventy-nine."

"Mobilize our troops. We are moving it to number one."

―Wat Tambor and TA-175


Ryloth is a planet with cities. The planet's road network can be represented by a binary tree, such that each vertex represents a city of Ryloth, and each edge represents a road connecting two cities. Road is the only available transportation in Ryloth.

Ryloth has been warned about the sinister plans of the separatists, and just in time. The planet of Ryloth has just enough forces to defend against the attack. However, the forces have not been optimally stationed and need to be moved quickly to counter the attack.

For each city , there is a non-negative integer representing the number of battalions currently located at that city. All battalions are well trained and are equally good. It costs exactly 1 republic credit to move a single battalion from a city to one of its adjacent cities.

Thanks to republic intelligence, it is known exactly how many battalions are required in each city to defend it succesfully. For each city , the number of battalions required to defend it is . Moreover, Ryloth has just enough soldiers to defend against the attack. That is, .

Ryloth must mobilize its Army quickly so that each city has enough number of battalions to defend it. To do that, some battalions have to be moved between cities. The prime minister of Ryloth obviously wants to minimize the total cost of moving the army.

Given the road network in Ryloth and the values of and for each city, find out the minimal cost of moving the army to defend against the attack.

Note: Time limit for this problem for different languages:

  • C/C++: 1 sec
  • Java: 2 sec
  • Python2/3: 5 sec

Input Format

The first line contains a single integer . The next lines contain two integers each, the values of and . The next lines contain two integers each, indicating that there is an edge from to .

Constraints:

  • The given edges form a binary tree

Output Format

Print a single integer in one line denoting the minimum cost of relocating.

Sample Input

4
0 7
6 2
5 3
1 0
0 1
0 2
1 3

Sample Output

8

Explanation

One way to move battalions is:

  • move 2 battalions from city 2 to city 0 (cost 2).
  • move 4 battalions from city 1 to city 0 (cost 4).
  • move 1 battalions from city 3 to city 0 (cost 2).

total cost = 2 + 4 + 2 = 8

Line: 1 Col: 1
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score