ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ural SU contest. Petrozavodsk training camp. Summer 2010

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

G. Замкадье

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
В королевстве Замкадье, расположенном на Великой Равнине, n городов. Давным-давно основатель королевства построил n − 1 прямую двустороннюю дорогу. От любого города по этим дорогам можно было добраться до любого другого города. Основатель был очень бережлив, поэтому суммарная длина этих дорог была минимально возможной.
Король Замкадья Карл I на старости лет решил отправиться в путешествие и посетить все города своего королевства. Он начал своё путешествие в городе Понаеховске, где располагался королевский дворец, и действовал следующим образом:
  • Если Карл I приезжал в город, где до этого не был, он детально описывал свои впечатления в дневнике и запоминал город, откуда он попал в этот.
  • Если из города, где находился Карл I, какая-нибудь дорога вела в город, где он ещё не был, то он ехал по ней. В противном случае Карл I возвращался в город, откуда он впервые попал в данный.
Вскоре после путешествия Карл I умер, завещав свой дневник сыну, Карлу II.
Прошло много лет. Карл II состарился и решил посетить все города королевства в том порядке, в котором они были описаны в дневнике его отца. Техника за прошедшие годы шагнула далеко вперёд, и Карл II собрался путешествовать на дирижабле — на нём можно от любого города до любого другого лететь напрямик, не пользуясь дорогами. Карл II был более ленив, чем его отец, поэтому решил посетить все города ровно по одному разу, после чего вернуться в Понаеховск.
К вам за помощью обратилась жена Карла II. Она хочет знать, когда вернётся её муж, но ей неизвестен порядок городов, в котором они описаны в дневнике. Вычислите минимально возможное расстояние, которое придётся преодолеть Карлу II.

Исходные данные

В первой строке записано целое число n (2 ≤ n ≤ 1 000) — количество городов в Замкадье. Города занумерованы числами от 1 до n, Понаеховск имеет номер 1. В i-й из следующих n строк через пробел записаны два целых числа — координаты i-го города. Координаты не превосходят по модулю 10 000. Любые два города расположены в различных точках. Далее следует пустая строка, после которой в n − 1 строке описываются дороги Замкадья. Каждая дорога задаётся парой номеров городов, которые она соединяет, записанных через пробел.

Результат

Выведите минимальное расстояние, которое придётся преодолеть Карлу II на дирижабле, с относительной погрешностью не более 10−9.

Пример

исходные данныерезультат
4
0 0
1 0
1 1
0 1

1 2
1 4
4 3
4.000
Автор задачи: Александр Ипатов
Источник задачи: Ural SU Contest. Petrozavodsk Summer Session, August 2010
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1847. Замкадье