1 人解决，4 人已尝试。
1 份提交通过，共有 8 份提交。
9.9 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
Jill is a human-resource manager at a big software company. As this year was quite successful from a business perspective, she wants to give out small gifts for the holiday season to every employee. In order to make the employees feel special, she wants to make sure that everybody gets a gift that is unique across the group of people that he or she works with. Fortunately, the software company has a very strict hierarchy, where people only work with their immediate boss and the people that are directly reporting to them.
Since Jill is a smart girl, she recognizes that she will only need two different gifts to make everybody feel special. She easily found two nice gifts which are, however, priced slightly differently. Always trying to save money for her company, she wonders how to assign the gifts to employees so that she has to spend the least possible amount of money. Can you help her?
You are given the price of the two gifts Jill has chosen, together with the information which employee is reporting to whom. You should compute the minimum cost of an assignment of gifts to employees that fulfills the following condition: if an employee receives a certain gift, it must be different from the gift his boss receives and no one directly reporting to him may receive the same gift.
The first line contains the number of scenarios. Each scenario begins with a line containing two integers u and v (1 <= u, v <= 1 000), the prices of the two gifts. The rest of the scenario describes the company’s employees. It starts with a line containing the number of employees n (2 <= n <=1 000). The next line will contain n - 1 numbers b1, b2, . . . bn-1 separated by spaces, where bi is the boss of employee i. Directly or indirectly, everybody is reporting to the company’s CEO, who is identified by number 0. Note, that the CEO will receive a gift as well.
The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line with the minimum amount of money Jill has to spend for gifts. Terminate each scenario with a blank line.
2 7 4 12 0 0 1 2 2 2 3 3 3 5 5 3 5 3 2 0
Scenario #1: 63 Scenario #2: 11
1 人解决，4 人已尝试。
1 份提交通过，共有 8 份提交。
9.9 EMB 奖励。
创建: 18 年，5 月前.
修改: 7 年，2 月前.
最后提交: 6 年，10 月前.
来源: TUD Programming Contest 2006 (Training Session), Darmstadt, Germ