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

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

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian nickpros 2018-01-29 16:34:04 0 (опубликовано)
ru1 Russian nickpros 2018-01-29 16:31:14 922 Первая редакция (сохранено в черновиках)