Не уверен, но кажется в задаче С с регионалки неполный набор тестов. После завершения контеста я поспрашивал решения у своих друзей и с удивлением обнаружил, что большинство из них С решало так: найдем диаметр дерева и его глубину, тогда рассмотрим поддеревья конца диаметра исходного дерева, в них пройдем по глубинам исходного дерева и соединим их по диаметру.
Это решение неверное. Причина: из условия можно сделать вывод, что корень дерева не является листом (потому что у него есть дети), а потому если диаметр кончается в корне, мы не можем подвешивать к нему степени. Соответственно решение должно выводить неверный ответ.
Контртесты подбираются легко: в них диаметр должен кончаться в корне (и при этом степень корня равна единице). В частности, подходит бамбук. Например, при n = 3, m = 2 ответ будет 6, в то время как вышеописанное решение выведет 9.
Автокомментарий: текст был обновлен пользователем nickpros (предыдущая версия, новая версия, сравнить).
День добрый. Я автор идеи и я же готовил задачу.
Да, там нет ни одного теста в котором степень корня равна 1. Более того это изначально так и планировалось (увы) и это ограничение есть даже в валидаторе.
Дело в том, что когда я предлагал задачу формулировка была дана для не подвешенных деревьев (просто осуществлялось подвешивание ко всем листам дерева), но с выделенной специальной вершиной (она же корень в текущей версии) и если эта вершина является листом, то это вносит некоторые неудобства в том, что к нему тоже подвешивают (в отличии от "корневой" версии в которой корень просто не считается как лист и такого не происходит).
Условие писали немного другие люди, и я немного протормозил в этом месте, а потом случилось тестирование и менять тесты было поздно.
Я сильно извиняюсь и надеюсь это не сильно подпортило вам впечатление от задачи и региона в целом.
У нас было много дурацких вопросов о том, "если у корня только один потомок, то это лист", и были вопросы типа "А верно ли что дерево — не бамбук"? При этом условия допускали бамбук и условие задачи оставалось корректным. Но в разборе случай бамбука не рассматривался. Тогда мы уточнили и узнали, что тестов на бамбук нет (и узнали, что авторами задачи бамбук и не предполагался). Общего объявления делать не стали, ибо условия были корректны.