## APIO '14 P3 - Beads and Wires

View as PDF

Points: 25 (partial)
Time limit: 0.6s
Memory limit: 128M

Problem types

A popular child game at the time of Leonardo was called Beads-and-wires. Not surprisingly, it was played with beads and wires. The wires are red or blue. The beads are numbered from to . The game starts with a single bead. From this moment on, new beads can be added using wires as follows.

• Append : a new bead is attached to an existing bead through a piece of red wire.
• Insert : a new bead is inserted by substituting an already existing red wire connecting existing beads and , with two new blue wires by putting between and ; in other words, the existing red wire is replaced by two new blue wires and .

Every piece of wire (both blue or red) has a certain length. At the end of the game, what counts is the sum of lengths of blue wires only (the length of red wires doesn't count): this is called the final score.

You are given the final configuration reached by a beads-and-wire game, specifying how beads are connected to one another and providing also the length of each piece of wire, but omitting the color of the wires.

You have to write a program that finds the maximal possible final score for that configuration. More precisely, among all the feasible beads-and-wire games that end with that configuration, you have to find one that has the maximum final score (sum of blue wire length) and you have to output that value.

#### Input Specification

First line contains positive integer — number of beads, which are numbered from to . Next lines contains 3 numbers each: and — two beads connected by a piece of wire, and the length of that piece.

#### Output Specification

Output one integer – the maximum final score.

#### Scoring

Your program will be tested on 4 sets of input instances as follows:

#### Sample Input 1

5
1 2 10
1 3 40
1 4 15
1 5 20

#### Sample Output 1

60

#### Explanation for Sample Output 1

For the first sample testcase, the final score of can be obtained as follows: start with the single bead .

• append to (with a wire of arbitrary length).
• insert on the wire (using wires of length and ).
• append to with a wire of length .
• append to with a wire of length .

The configuration obtained this way is shown in the first figure. It is possible to see that there is no way to obtain the same configuration (apart for the colors) with a larger final score.

#### Sample Input 2

10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34

#### Sample Output 2

140

#### Explanation for Sample Output 2

For second sample testcase the configuration obtained this way is shown in the second figure, and has a final score of .