Региональный этап ВсОШ, день 2, задача С
Разница между ru1 и ru2, 0 символ(ов) изменены
Не уверен, но кажется в задаче _С_ с регионалки неполный набор тестов. После завершения контеста я поспрашивал решения у своих друзей и с удивлением обнаружил, что большинство из них _С_ решало так: найдем диаметр дерева и его глубину, тогда рассмотрим поддеревья конца диаметра исходного дерева, в них пройдем по глубинам исходного дерева и соединим их по диаметру.↵

**Это решение неверное**. Причина: из условия можно сделать вывод, что **корень дерева не является листом** (потому что у него есть дети), а потому если диаметр кончается в корне, мы не можем подвешивать к нему степени. Соответственно решение должно выводить неверный ответ.↵

Контртесты подбираются легко: в них диаметр должен кончаться в корне (и при этом степень корня равна единице). **В частности, подходит бамбук**. Например, при n = 3, m = 2 ответ будет 6, в то время как вышеописанное решение выведет 9.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru2 Русский nickpros 2018-01-29 16:34:04 0 (опубликовано)
ru1 Русский nickpros 2018-01-29 16:31:14 922 Первая редакция (сохранено в черновиках)