Два игрока, Красный и Синий, снова в деле, и этот раз они играют с цветными мелками! Сегодня озорной паре под руку попалось корневое дерево, с которым они играют в свою любимую игру, раскрашивая вершины этого дерева.
Игра выглядит следующим образом: есть дерево из \(n\) вершин с корнем в вершине \(1\), и каждая вершина первоначально белого цвета. У Красного и Синего есть ровно по одному ходу. Первым ходит Красный.
В свой ход, Красный может выполнить следующее действие произвольное количество раз:
- Он выбирает любое поддерево корневого дерева и красит каждую из вершин поддерева в красный.
Однако, для большей честности, Красный может покрасить только
\(k\) вершин дерева. Другими словами, после окончания хода Красного, не более
\(k\) вершин может быть покрашено в красный.
Далее подходит очередь Синего. Он может выполнять следующее действие произвольное количество раз:
- Он выбирает любое поддерево корневого дерева и красит каждую вершину поддерева в синий. Однако, ему нельзя выбирать поддеревья, в которых содержатся вершины, уже покрашенные в красный. Ведь в таком случае вершина получится фиолетового цвета, а никто не любит фиолетовый мелок* (англ. purple crayon).
Заметим, что нет ограничения на то, сколько вершин покрасит Синий, главное, что он не красит уже покрашенные Красным вершины.
После того как каждый сделает свой ход, счет игры определяется следующим образом: пусть \(w\) — количество оставшихся белых вершин, \(r\) — количество красных вершин, а \(b\) — количество синих вершин. Счет игры будет равен \(w \cdot (r - b)\).
Красный хочет максимизировать счет, а Синий — минимизировать. Чему будет равен счет игры, если оба игрока действуют оптимально?
Примечание
В первом наборе входных данных, одна из оптимальных стратегий следующая:
- Красный выбирает для покраски поддеревья вершин \(2\) и \(3\).
- Синий выбирает для покраски поддерево вершины \(4\).
В результате вершины
\(2\) и
\(3\) покрашены в красный,
\(4\) — в синий, а вершина
\(1\) — в белый. Счет игры равен
\(1 \cdot (2 - 1) = 1\).
Во втором наборе, оптимальная стратегия следующая:
- Красный выбирает для покраски поддерево вершины \(4\). Тем самым красит вершины \(4\) и \(5\).
- Синий не может ничего выбрать, а потому ничего не красит.
В результате вершины
\(4\) и
\(5\) покрашены в красный, а вершины
\(1\),
\(2\) и
\(3\) — белые. Счет игры равен
\(3 \cdot (2 - 0) = 6\).
В третьем наборе:
Счет игры равен \(4 \cdot (2 - 1) = 4\).