Битва с боссами

Автор задачи и разработчик: Даниил Голов

Давайте формализуем условие задачи. Есть подвешенное дерево из $$$n$$$ вершин и процесс, состоящий из двух чередующихся стадий — сначала из дерева убираются все вершины, являющиеся единственным ребенком своего родителя, а затем вершина с самым большим числом детей становится вершиной с одним ребенком.

Соответственно,

Таким образом, ситуация, когда Зельда не может победить никого из боссов, может возникнуть исключительно тогда, когда босс остался всего один.

Заметим, что корень дерева при любом перестроении останется корнем. Действительно, если у корня максимальное число детей, то выберется сын корня и на следующей стадии он же удалится. Если у корня не максимальное число детей, перестроений с ним не будет. Также заметим, что сам корень дерева никогда не удаляется, так как Зельда атакует только боссов, у которых есть предок.

Таким образом, всё, что требовалось в задаче — найти корень заданного дерева и вывести его номер. Для этого достаточно считать список детей каждой вершины и найти единственную вершину, которая не вошла ни в один из них.