Задача №3303. Islands
Вы гуляете в парке, где есть \(N\) островов. Когда-то с каждого острова \(i\) перекинули по одному мосту длиной \(L_i\). Всего мостов в парке \(N\). Несмотря на то, что мосты строились по направлению от одного острова к другому, сейчас по ним можно ходить в любом направлении. Также между каждой парой островов ходит паром.
Гулять вам нравится больше, чем кататься на паромах, поэтому вы решили максимизировать суммарную длину мостов, по которым вы пройдёте, соблюдая следующие ограничения:
- Можно начать путь на любом острове.
- Нельзя посетить остров дважды.
- В любой момент можно отправиться с текущего острова \(S\) на другой,
ранее не посещённый остров \(D\). Можно добраться с \(S\) на \(D\):
- Пешком, если между этими островами есть мост. В таком случае длина этого моста добавляется к суммарной длине пройденных мостов.
- Паромом. Этот вариант можно выбрать, только если \(D\) недостижим из \(S\) по любой комбинации мостов и/или уже использованных паромов. (При проверке достижимости рассматриваются все пути, включая проходящие уже посещённые острова.)
Заметьте, что необязательно посещать все острова и может оказаться невозможно пройти все мосты.
Даны описания мостов. Найдите максимальное расстояние, которое можно пройти по указанным правилам.
Первая строка ввода содержит единственное целое число \(N\) — количество островов в парке (\(2 \le N \le 1\,000\,000\)). Острова нумеруются целыми числами от \(1\) до \(N\).
Каждая из следующих \(N\) строк описывает мост. \(i\)-я строка описывает мост, ведущий с острова \(i\) двумя целыми числами: первое из них задаёт номер острова, с которым мост соединяет \(i\)-й остров, второе — длину \(L_i\) этого моста. Длина — натуральное число, не превышающее \(100\,000\,000\).
Выведите одну строку, содержащую единственное целое число — максимальное возможное расстояние, которое можно пройти по мостам.
\(N = 7\) мостов в примере таковы: \((1-3)\), \((2-7)\), \((3-4)\), \((4-1)\), \((5-1)\), \((6-3)\) и \((7-2)\). Заметьте, что два различных моста соединяют острова 2 и 7.
Один из способов получить максимальное расстояние таков:
- Начать с острова 5.
- Пройти по мосту длины 9 и оказаться на острове 1.
- Пройти по мосту длины 8 и оказаться на острове 3.
- Пройти по мосту длины 4 и оказаться на острове 6.
- Переправиться на пароме на остров 7.
- Пройти по мосту длины 3 и оказаться на острове 2.
В конце вы окажетесь на острове 2, и суммарное расстояние будет равно \(9+8+4+3 = 24\). Единственный остров, оставшийся непосещённым, — 4. Заметьте, что по окончании описанного путешествия ни один остров больше посетить нельзя. Более точно:
- Нельзя отправиться туда пешком, так как нет моста, соединяющего 2 (текущий остров) и 4.
- Нельзя воспользоваться паромом, так как 4 достижим из 2, где вы теперь находитесь. Способ его достичь: воспользоваться мостом \((2-7)\), затем переправиться на пароме, которым вы уже переправлялись с острова 7 на остров 6, затем мост \((6-3)\) и, наконец, мост \((3-4)\).
7 3 8 7 2 4 2 1 4 1 9 3 4 2 3
24