提示: 欢迎访问OurACM平台。
Problem 2269 Picking Game

Accept: 1    Submit: 35
Time Limit: 3000 mSec    Memory Limit : 32768 KB

Problem Description

Fat brother and Maze are playing a kind of special (hentai) game in a weighted tree. In this game, players can pick vertexes in this tree; both of them get 0 point at first. In one player’s turn, he/she can pick a vertex and then sum the weight which is assigned to this vertex to his/her score. They keep doing this one by one which means that after Fat Brother picks his vertex, Maze would picks another one and vice versa. But there is a restriction, when a player picks a vertex; he/she must pick a vertex which is adjacent to the previous one he/she picked in the tree. The picking action is mandatory which means that a player cannot skip his/her own turn at any time. Also, a vertex can be picked at most once which means that if a vertex has been picked by one of the players; no one can pick this vertex in later rounds. Fat Brother always begins the game by picking the vertex 1, and Maze would pick vertex 2 as follow.

The game ends when both players have no vertex to pick. If one of the players has no vertex to pick, the other player can still take actions and skips another player’s turn until both of them have no vertex to pick. The player with the highest points wins this game and they would have a tie if they get the same points.

You can assume that both Fat Brother and Maze are clever enough, in his/her own turn; they always choose the action that benefits him/her most.

Input

The first line of the data is an integer T (1 <= T <= 1000), which is the number of the text cases.

Then T cases follow, each case contains an integer N (2 <= 100000 <= N) indicated the number of the vertexes in this tree. Then a line with N integers indicates the weight of each vertex in this tree. Then goes N-1 lines with two integers x and y (1 <= x, y <= N) each line, which means that there is an edge connected vertex x and vertex y in this tree.

The weights of the vertexes in this tree are positive and no more than 1000.

In 90% of test cases, N <= 50.

Output

For each case, output the case number first, and then output the winner of this game. See the sample output for more details.

Sample Input

5 2 1 2 1 2 2 1 1 1 2 3 3 2 1 1 2 2 3 3 1 3 1 1 2 1 3 5 2 2 1 1 1 1 3 2 3 3 4 2 5

Sample Output

Case 1: Maze Case 2: Draw Game Case 3: Draw Game Case 4: Maze Case 5: Fat Brother

Hint

In the fifth case, Fat Brother picks the vertex 1 and scores 2 points at first, and then Maze starts her game with vertex 2 and scores 2 points. Then Fat Brother chooses vertex 3 and blocks Maze’s way. So now Maze can only picks vertex 5 and lose this game.

Source

第七届福建省大学生程序设计竞赛-重现赛(感谢承办方闽江学院)

Submit  Back  Status  Discuss