MemSQL Start[c]UP 2.0 - Round 2 |
---|
Закончено |
Pieguy и Piegirl играют в игру. У них есть корневое бинарное дерево, которое обладает следующим свойством: каждая вершина дерева либо лист, либо имеет ровно два сына. Каждый лист имеет некоторое значение, ассоциированное с ним.
Во время игры игроки по очереди делают ходы. На своем ходу игрок выбирает два листа, имеющих общего непосредственного предка, и удаляет их. При этом он ассоциирует с общим предком листов (после удаления он станет листом) какое-то одно из ассоциированных с ними значений на свой выбор. Игра заканчивается, когда в дереве остается ровно одна вершина — корень дерева.
Pieguy ходит первым и его цель — максимизировать значение, которое будет ассоциировано с корнем в конце игры. Piegirl, наоборот, хочет минимизировать это значение. Считая, что оба игрока играют оптимально, вычислите значение, которое будет ассоциировано с корнем в конце игры.
В первой строке записано целое число t (1 ≤ t ≤ 100) — количество тестовых данных. Далее идет описание t тестовых данных. Каждый тест начинается с пустой строки, за которой следует строка, содержащая целое число n (1 ≤ n ≤ 250) — количество вершин дерева. Затем следуют n строк, описывающих n вершин дерева. Если текущая строка описывает лист дерева, то в ней содержится одно неотрицательное целое число ai (0 ≤ ai ≤ 1000), обозначающее ассоциированное с этим листом значение. Иначе, сперва в строке записано число - 1, а затем два целых числа l и r (0 ≤ l, r ≤ n - 1) — номер левого и правого сыновей текущей вершины. Вершины дерева пронумерованы от 0 до n - 1. Корень дерева — это вершина с номером 0.
Для каждого теста в отдельной строке выведите ответ на задачу.
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
10
10
4
8
Название |
---|