Блог пользователя alibi

Автор alibi, история, 9 лет назад, По-русски

Как решить эту задачу?

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
9 лет назад, # |
Rev. 5   Проголосовать: нравится +6 Проголосовать: не нравится

1) В графе N вершин и Nребер. Следовательно граф — это цикл, к некоторым вершинам которого подвешены деревья. Явно выделим цикл + корни каждого из деревьев.

2) Самые удаленные вершины удалены на расстояние диаметра графа друг от друга. Найдем диаметр графа (http://mirror.codeforces.com/blog/entry/17974)

3) Осталось порисовать на бумажке, аккуратно разобрать несколько случаев + пошаманить с деревом отрезков на цикле.

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -7 Проголосовать: не нравится

    Самая сложная часть — пошаманить с деревом отрезков на цикле, но для меня наоборот — как решать для дерева?