프로그램 명: apio_beads
제한시간: 1 초
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 1 to n. The game starts
with a single bead. From this moment on, new beads can be added using wires as follows.
- Append(w, v): a new bead w is attached to an existing bead v through a piece of red wire.
- Insert(w, u, v): a new bead w is inserted by substituting an already existing red wire connecting
existing beads u and v, with two new blue wires by putting w between u and v; in other words, the
existing red wire u ? v is replaced by two new blue wires u ? w and w ? v.
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.
Note
For the first sample testcase, the final score of 60 can be obtained as follows: start with the single bead 3.
- append 5 to 3 (with a wire of arbitrary length).
- insert 1 on the wire 3 ? 5 (using wires of length 40 and 20).
- append 2 to 1 with a wire of length 10.
- append 4 to 1 with a wire of length 15.
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.
For second sample testcase the configuration obtained this way is shown in the second figure, and has a
final score of 140.
입력
First line contains positive integer n ? number of beads, which are numbered from 1 to n. Next n - 1
lines contains 3 numbers each: ai , bi (1 ≤ ai < bi ≤ n) and 1 ≤ ci ≤ 10000 - two beads connected by a piece of wire, and the length of that piece.
출력
Output one integer - the maximum final score.
입출력 예
입력
5
1 2 10
1 3 40
1 4 15
1 5 20
출력
60
입력
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
출력
140
출처:apio 2014
[질/답]
[제출 현황]
[푼 후(0)]