← 返回题目列表

Codeforces · 457/F

F. 一个关于树的简单问题

中文机器翻译题面 查看原题

Pieguy 和 Piegirl 正在玩游戏。它们有一个有根二叉树,其属性是每个节点要么是叶子,要么恰好有两个子节点。每片叶子都有一个与之相关的编号。

在他/她的回合中,玩家可以选择任何两个共享其直接父级的叶子,删除它们,并将它们的值与现在成为叶子的父级关联起来(玩家决定关联两个值中的哪一个)。当只剩下一个节点(即树的根节点)时,游戏结束。

Pieguy 先走,他的目标是在游戏结束时最大化与根相关的值。 Piegirl 希望最小化该值。假设两个玩家都处于最佳状态,那么当游戏结束时,与根相关联的数字是多少?

输入

第一行包含一个整数 t (1 ≤ t ≤ 100) — 测试用例的数量。然后是测试用例。每个测试用例以一个空行开始,后面跟着一行包含单个整数 n (1 ≤ n ≤ 250) 的行,然后是描述树的 n 个节点的 n 行。这 n 行中的每一行要么包含一个非负数 ai,指示与其关联的值 ai (0 ≤ ai ≤ 1000) 的叶节点,要么包含 - 1 后跟整数 l 和 r,指示具有子节点 l 和 r (0 ≤ l, r ≤ n - 1) 的非叶节点。节点编号从 0 到 n-1。根始终是节点 0。

输出

对于每个测试用例,打印一行,上面有一个整数——游戏结束时与根相关联的数字。

示例

输入 #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