ZOJ Problem Set - 3517
Once upon a time, there was a magical land. The land was full of magnificent scenery, but the most mysterious and most beautiful part, is the pearl of the land: the Tower Seven.
The Tower Seven was so magical. It contained several floors and several rooms, each room had a unique name. Every floor had some rooms, but the top floor had only one room. Each room had several entrance doors and one exiting door, but the room on the top floor had no exiting door, and each of the rooms on the ground floor had only one entrance door, so it can be entered from outside of the Tower Seven. The entrance doors and exiting doors were the same kind of doors, just marked as different ones. So people can walk through all those doors, both entrance door and exiting door - except went back through the entrance door of the ground floor to go out of the Tower Seven.
And, the most important thing, the whole tower was full of precious coral bids, and they were hanging on every room's exiting door(Of course the very door was another room's entrance door). If someone took all the bids away, the same amount of bids appeared in the same place immediately.
Every year in the ancient magical land, there would be a celebration. During the celebration, k warriors would went into the tower from the ground floor. They passed through some rooms, and meet in one room. They could went through some rooms that others had visited or visiting, but they couldn't went into any rooms that had already been visited by himself or outside the tower, and any pair of them cannot have a totally same path of rooms.
They could went through any doors, no matter the entrance door or the exiting door. When passing one door, they must carry all bids hanging on that door(On the side marked as exiting door). When they meet in one room, they gather all coral bids they carried, and count the total number of coral bids. Their mission was find out the plan that can get the largest number of coral bids.
Some thing you have to know, is that from any room of the Tower Seven, people can always went to every other rooms through some exiting doors and/or entrance doors. And, between any pairs of rooms, there would be only one path from one to the other.
You can get some useful information from sample input and sample output.
There are several test cases. Each case begins with a line which contains two integers n(4 ≤ n ≤ 10000) and k(1 ≤ k < n, k ≤ 500), n indicates the number of rooms in the Tower Seven, and k indicates the number of warriors. Then the following n - 1 lines described the n - 1 rooms(except the room on the top floor), every line contains a string name, another string exit_room and an integer count. name is the room's name, exit_room is the name of the room which the exiting door leads to. Both name and exit_room are in the set of all the rooms' names, the length of every room's name is in range [2..10], and all the characters of rooms' names is in lowercase. count(1 ≤ count ≤ 20) is the number of coral bids hanging on the exiting door of the room.
We promise that there are at least k rooms on the ground floor.
For each test case, output the largest number of coral bids the k warriors can get in one line.
4 3 leafa root 5 leafb root 7 leafc root 4 5 3 la rr 1 lb nn 1 lc nn 1 nn rr 1
In the first sample, there are three warriors, they meet in room "leafb", and in the second sample, the three warriors meet in room "la".
Author: FAN, Yuzhe
Contest: ZOJ Monthly, July 2011