Модуль: Хеширование


Задача

8 /8


Бункеры

Теория Нажмите, чтобы прочитать/скрыть


Существует также несколько способов эффективно хэшировать корневые деревья. 
Один из таких способов устроен следующим образом:
Обрабатываем вершины рекурсивно, в порядке обхода в глубину. Будем считать, что хэш единичной вершины равен p. Для вершин с детьми, мы сперва запускаем алгоритм для них, затем через детей будем считать хэш текущего поддерева. Для этого рассмотрим хэши поддеревьев детей как последовательность чисел и посчитаем хэш от этой последовательности. Это и будет хэшом текущего поддерева.
Если нам не важен порядок на детях, то до подсчета хэша, отсортируем последовательность хэшей от поддеревьев детей и затем посчитаем хэш от отсортированной последовательности.

Таким образом можно проверять изоморфизм деревьев - просто считаем хэш без порядка на детях (то есть каждый раз сортируя хэши детей). И если хэши корней совпадают, то деревья изоморфны, иначе нет.

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

Задача

Петя и Вася с упоением играют в шпионов. Сегодня они планируют, где будут 
расположены их секретные бункеры и штаб-квартира. 

Пока Петя и Вася решили, что им понадобится ровно n бункеров, которые для секретности будут пронумерованы числами от 1 до n. 
Некоторые из них будут соединены двусторонними тоннелями, причем для надежности и секретности по тоннелям можно будет попасть из любого бункера в любой единственным образом.
Петя и Вася даже решили, какие из бункеров будут соединены тоннелями, но выбрать, какой из них будет штаб-квартирой, они не могут. 
Мальчики хотят выбрать ее и разделить оставшиеся бункеры между собой таким образом, чтобы им досталось поровну бункеров к штаб-квартире вело бы ровно два тоннеля: один от бункера, принадлежащего Васе, другой - от бункера, принадлежащего Пете. 
                                                                                   
Уставший Петя пошел к себе домой, а утром Вася показал ему план, на котором бункеры были обозначены точками, а тоннели отрезками. 
Кроме того, Вася выбрал штаб-квартиру таким образом, что нарисованный им план был симметричен относительно прямой, проходящей через точку, которая соответствовала штаб-квартире.
 
Хотя Петя почти сразу показал Васе, что тот ошибся и не нарисовал половину бункеров, ему стало интересно, можно ли выбрать штаб-квартиру и нарисовать такой симметричный план.

Входные данные:
В первой строке входного файла находится одно целое число n (1 <= n <= 105) - количество бункеров. 
В следующих n - 1 строках находится по два целых числа ui и vi (1 <= ui, vi <= n, ui ≠ vi) - номера бункеров, которые соединяет i-ый тоннель. 
Гарантируется, что между любыми двумя бункерами существует единственный путь.

Выходные данные:
В выходной файл выведите "YES", если можно выбрать штаб-квартиру и нарисовать такой план, или "NO" если это невозможно.

Примеры:
 
Входные данные Выходные данные
2
1 2
NO
3
1 2
2 3
YES

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w641
Комментарий учителя