Задача №114685. Игра на дереве
Глеб и Коля играют в игру на дереве (связном графе без циклов). Они ходят по очереди, Глеб ходит первым. На своем первом ходу каждый игрок ставит свою фишку в любую вершину дерева, но Коля не может поставить свою фишку в вершину, в которой стоит фишка Глеба.
На каждом следующем своем ходу игрок перемещает свою фишку из вершины по какому-то ребру в соседнюю вершину. Игроки не могут перемещать фишку в вершину, в которой когда-то была или сейчас находится одна из фишек. Проигрывает тот, кто не может сделать ход.
Определите, может ли выиграть Глеб при оптимальной игре обоих игроков.
В первой строке дано целое число \(t\) — количество тестовых случаев (\(1 \le t \le 100\,000\)).
В первой строке каждого тестового случая дано одно целое число \(n\) — количество вершин в дереве (\(2 \le n \le 100\,000\)).
В следующих \(n - 1\) строках дано по два целых числа \(a_i\) и \(b_i\) — номера вершин, соединенных ребром (\(1 \le a_i, b_i \le n\)). Гарантируется, что вам дано дерево.
Сумма \(n\) по всем тестовым случаям в одном тесте не превышает \(100\,000\).
Для каждого тестового случая, если Глеб может выиграть, в новой строке выведите « Yes », иначе выведите « No ».
Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех предыдущих групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
Обозначим сумму всех \(n\) в одном тесте за \(N\).
| Дополнительные ограничения | |||
| Группа | Баллы | \(N\) | Комментарий |
| 0 | 0 | – | Тесты из условия. |
| 1 | 14 | \(N \le 20\) | |
| 2 | 25 | \(N \le 300\) | |
| 3 | 29 | \(N \le 3\,000\) | |
| 4 | 32 | – | Offline-проверка. |
2 3 1 2 2 3 8 1 3 3 5 3 7 1 6 1 4 4 2 5 8
Yes No