NOI '11 P4 - Road Construction - DMOJ: Modern Online Judge

NOI '11 P4 - Road Construction

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 1.5s

Memory limit: 256M

Problem type

National Olympiad in Informatics, China, 2011

On planet W, there exist $n$ ~n~ countries. To promote the economic growth of each country, the kings of the countries have decided to construct bidirectional roads to ensure that all countries are connected. However, since they're all incredibly stingy, they wish to construct exactly $n-1$ ~n-1~ roads.

Constructing each road will require a cost. This cost is equal to the length of the road multiplied by the absolute difference of the number of countries on each side of the road. For example, the road represented by a dashed line in the figure below has, respectively, $2$ ~2~ and $4$ ~4~ countries on each of its sides. If this road has a length of $1$ ~1~, then the cost will be $1 \times |2-4| = 2$ ~1 \times |2-4| = 2~. The circled numbers represent the numbers of the countries.

$\text{[math]}$

Since both the number of countries and the number of ways to construct the roads are extremely large, as well the construction costs for each way is hard to calculate by humans, the kings have decided to hire a person to design a software to do this. This piece of software should be able to calculate the total cost of constructing all the roads, given a way to construct them. Please help the kings to write such a program.

Input Specification

The first line will contain an integer $n$ ~n~, representing the number of countries on planet W. Countries are numbered from $1$ ~1~ to $n$ ~n~.
For the following $n-1$ ~n-1~ lines, each line will describe the construction of a single road. The $i$ ~i~-th of these lines will contain three integers $a_i$ ~a_i~, $b_i$ ~b_i~, and $c_i$ ~c_i~, indicating that the $i$ ~i~-th bidirectional road connects countries $a_i$ ~a_i~ and $b_i$ ~b_i~, and has a length of $c_i$ ~c_i~.

Output Specification

Output a single integer, the total cost of constructing all the roads.

Sample Input

Sample Output

Constraints

The attributes of all the test cases are outlined below.

Test Case	Size of $n$ ~n~ (Note the $=$ ~=~, not $\le$ ~\le~)	Constraints
$1$ ~1~	$n = 2$ ~n = 2~	$1 \le a_i, b_i \le n$ ~1 \le a_i, b_i \le n~ $0 \le c_i \le 10^6$ ~0 \le c_i \le 10^6~
$2$ ~2~	$n = 10$ ~n = 10~
$3$ ~3~	$n = 100$ ~n = 100~
$4$ ~4~	$n = 200$ ~n = 200~
$5$ ~5~	$n = 500$ ~n = 500~
$6$ ~6~	$n = 600$ ~n = 600~
$7$ ~7~	$n = 800$ ~n = 800~
$8$ ~8~	$n = 1000$ ~n = 1000~
$9$ ~9~	$n = 10\,000$ ~n = 10\,000~
$10$ ~10~	$n = 20\,000$ ~n = 20\,000~
$11$ ~11~	$n = 50\,000$ ~n = 50\,000~
$12$ ~12~	$n = 60\,000$ ~n = 60\,000~
$13$ ~13~	$n = 80\,000$ ~n = 80\,000~
$14$ ~14~	$n = 100\,000$ ~n = 100\,000~
$15$ ~15~	$n = 600\,000$ ~n = 600\,000~
$16$ ~16~	$n = 700\,000$ ~n = 700\,000~
$17$ ~17~	$n = 800\,000$ ~n = 800\,000~
$18$ ~18~	$n = 900\,000$ ~n = 900\,000~
$19$ ~19~	$n = 1\,000\,000$ ~n = 1\,000\,000~
$20$ ~20~	$n = 1\,000\,000$ ~n = 1\,000\,000~

Problem translated to English by Alex.

Comments

There are no comments at the moment.