На контесте https://codeforces.com/contest/1061 я сдал задачу F, но уверен, что мое решение не правильное.. может кто объяснить как оно зашло?
Вообщем идея заключается в том, что бы взять две вершины А и Б и с помощью простых манипуляций сделать их листьями(просто перебираем С и если на пути из С в Б содержится А, то А становится С, тоже проделываем с Б) теперь у нас есть 2 листа. Дальше я делаю так: нахожу вершину которая является их lca и если эта вершина = корень(проверяется с помощью высоты дерева), то вывожу ответ, иначе я отставляю А листом, а Б делаю равным любой вершине, такой, что путь из А в эту вершину содержит lca. (НЕ РАНДОМНО). так вот есть проблема: мое решение должно падать всегда, когда мы после lca Б делаем равную одному из потомков lca.. тогда программа будет циклиться бесконечно и будет ТЛ.. я отправил это решение 3 раза и они все зашли.. неужели просто везет и никогда не появляется теста, где я захожу в потомка lca?
И да, единственный рандом который у меня есть это на начальные А и Б.. без него ТЛ 18
Comments (0)
