An easy problem about trees

题意翻译

两个人在玩游戏。 有一棵二叉树$T$，恰有$n$个节点，每个节点要么是叶子节点要么有两个儿子。每个叶子节点上写了一个非负整数。 两个人轮流操作，每次选择两个有共同父亲的叶子节点，然后从两个叶子节点的数中选择一个填到父亲节点上，接着两个叶子节点会被删除，而父亲节点就变成了叶子节点。 很明显，在若干次操作后将只剩下根节点和它上面的数。先手的目标是最大化这个数；后手的目标是最小化这个数。你需要计算，在双方都采取最优策略的情况下，最终这个数是多少？

题目描述

Pieguy and Piegirl are playing a game. They have a rooted binary tree, that has a property that each node is either a leaf or has exactly two children. Each leaf has a number associated with it. On his/her turn a player can choose any two leafs that share their immediate parent, remove them, and associate either of their values with their parent, that now became a leaf (the player decides which of the two values to associate). The game ends when only one node (the one that was the root of the tree) is left. Pieguy goes first, and his goal is to maximize the value that will be associated with the root when the game ends. Piegirl wants to minimize that value. Assuming that both players are playing optimally, what number will be associated with the root when the game ends?

输入输出格式

输入格式

First line contains a single integer $ t $ ( $ 1<=t<=100 $ ) — number of test cases. Then $ t $ test cases follow. Each test case begins with an empty line, followed by a line with a single integer $ n $ ( $ 1<=n<=250 $ ), followed by $ n $ lines describing $ n $ nodes of the tree. Each of those $ n $ lines either contains a non-negative number $ a_{i} $ , indicating a leaf node with value $ a_{i} $ ( $ 0<=a_{i}<=1000 $ ) associated with it, or $ -1 $ followed by integers $ l $ and $ r $ , indicating a non-leaf node with children $ l $ and $ r $ ( $ 0<=l,r<=n-1 $ ). Nodes are numbered from $ 0 $ to $ n-1 $ . The root is always node $ 0 $ .

输出格式

For each test case print one line with one integer on it — the number that will be associated with the root when the game ends.

输入输出样例

输入样例 #1

4

3
-1 1 2
10
5

5
-1 1 2
-1 3 4
10
5
20

7
-1 1 2
-1 3 4
-1 5 6
1
2
3
4

11
-1 1 2
-1 3 4
-1 5 6
-1 7 8
15
7
-1 9 10
7
8
9
11

输出样例 #1

10
10
4
8