e-olymp
Соревнования

Least Common Ancestor

Поход в кино

prb4463 Чип и Дейл помогают всем в стране iLandia. Как-то после удачного завершения своих миссий они решили сходить в кино. Но тут их поджидала неожиданность! В стране есть только 1 кинотеатр, который находится в столице. Чип завершил свои приключения в городе x, а Дейл в городе y. До начала сеанса осталось мало времени, поэтому оба решили заказать такси, чтобы успеть к началу сеанса. Так как гонорары наших героев небольшие, то каждый желает потратить на такси как можно меньше денег. Чип может подсесть в такси к Дейлу и наоборот, если они оказались в одном городе. Так как у таксистов iLandии постоянная такса за километр, то затраты на путь, который они проехали вдвоем, делят на 2. Вам задано несколько сценариев завершения приключений Чипа и Дейла в разных городах. Для каждого сценария нужно посчитать минимальные вознаграждения героев, чтобы они смогли попасть в кино.

Между двумя произвольными городами существует только одна дорога, по которой между ними можно проехать. Расстояние между любыми двумя соседними городами (между которыми существует прямая дорога) составляет 1 километр. Столица всегда имеет номер 1.

Входные данные

В первой строке находится два натуральных числа: количество городов n (1n105) в iLandia, и цена Price (1Price104) за 1 км в стране. Каждая из следующих n - 1 строк содержит 2 натуральных числа x и y (1x, yn), описывающих наличие дороги из города x в город y. Все дороги двухсторонние. В следующей строке задается количество сценариев q (1q105). Каждый сценарий начинается с новой строки и задаётся номерами городов c и d (1c, dn), в которых заканчивают свои приключения соответственно Чип и Дейл.

Выходные данные

Вывести два числа: затраты Чипа и Дейла на дорогу с точностью не менее 10-5.

Лимит времени 1 секунды
Лимит использования памяти 128 MiB
Входные данные #1
3 2
1 2
1 3
3
2 3
1 2
1 3
Выходные данные #1
2 2
0 2
0 2
Автор Остап Столярчук
Источник Дистанционная Летняя Компьютерная Школа - лето 2013 года