CF457F An easy problem about trees

Pieguy 和 Piegirl 正在玩一个游戏。他们有一棵有根二叉树，这棵树具有这样的性质：每个结点要么是叶结点，要么恰好有两个子结点。每个叶结点都有一个与之关联的数值。 每位玩家在他的回合内，可以选择任意一对有相同父母的叶结点，将它们移除，并将其中一个的值（由当前玩家选择）赋予它们的父结点。该父结点此时变为叶结点。游戏结束时，只剩下一个结点（即原树的根结点）。 Pieguy 先手，并希望最终根结点获得尽可能大的值；而 Piegirl 则希望该值尽可能小。假设两人都采取最优策略，最终根结点上的数值是多少？

第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。接下来是 $t$ 个测试用例，每个测试用例前有一个空行。每个测试用例由一行整数 $n$（$1 \leq n \leq 250$）开始，表示该树有 $n$ 个结点。随后的 $n$ 行描述了 $n$ 个树结点。每一行要么包含一个非负整数 $a_{i}$，表示这是一个叶结点且其值为 $a_{i}$（$0 \leq a_{i} \leq 1000$）；要么包含 $-1$ 和两个整数 $l$ 和 $r$，表示这是一个非叶结点，其左右子结点编号分别为 $l$ 和 $r$（$0 \leq l, r \leq n-1$）。结点编号为 $0$ 到 $n-1$，根结点总是编号 $0$。

对于每个测试用例，输出一行一个整数，表示最终根结点上的数值。

由 ChatGPT 5 翻译