....как решать эту задачу:
Двое играют в следующую игру: имеется дерево с отмеченной вершиной (корнем). За ход игрок разрубает ветку (стирает ребро), причем из двух получившихся компонент связности остается только та, которая содержит корень, другая удаляется. Проигрывает тот, кто не может сделать ход. Определите, может ли выиграть первый игрок, и если да, то укажите любой из его выигрышных ходов.
В первой строке вводится 2 числа — количество вершин 1 < N ≤ 100000 и номер корня 1 ≤ R ≤ N. В следующих N – 1 строках идут пары чисел — описания ребер.
Формат выходных данных
В первой строке выведите число 1 или 2 – номер победителя при правильной игре.
Если побеждает первый игрок, то во второй строке выведите порядковый номер ребра во входных данных, которое ему достаточно разрубить первым ходом (число от 1 до N – 1).
Прошу подсказать идею решения
Если стереть ребро в дереве, то будет 2 дерева - получили сумму игр.
edit: а, не, фигню написал.
edit2: если к дереву прицепить ещё одну вершину (сделать ребро из неё в корень), и сказать, что это корень - функция Гранди такого дерева будет на единицу большей, чем у того, которое было.
спасибо, вроде очевидно, но как то не допер(
P.S. кончено проще минусовать, чем написать 1 предложение
Если есть несколько подветок дерева из корня - это прямая сумма игр, теорему про ним-сумму гугли.
Если есть только одно ребро - то число нима вершины это 1 + число нима этого потомка. Доказывается самокорректностью.
Найди ее разбор, а пока (ты знаешь правила)
Мопэд не его, он просто разместил объяву!