Задачи
Поход в кино
Поход в кино
\includegraphics{https://static.e-olymp.com/content/1f/1f3bec9ebf808c393192ff8c5c671445179b8a36.jpg}
Чип и Дейл помогают всем в стране iLandia. Как-то после удачного завершения своих миссий они решили сходить в кино. Но тут их поджидала неожиданность! В стране есть только $1$ кинотеатр, который находится в столице. Чип завершил свои приключения в городе $x$, а Дейл в городе $y$. До начала сеанса осталось мало времени, поэтому оба решили заказать такси, чтобы успеть к началу сеанса. Так как гонорары наших героев небольшие, то каждый желает потратить на такси как можно меньше денег. Чип может подсесть в такси к Дейлу и наоборот, если они оказались в одном городе. Так как у таксистов iLandии постоянная такса за километр, то затраты на путь, который они проехали вдвоем, делят на $2$. Вам задано несколько сценариев завершения приключений Чипа и Дейла в разных городах. Для каждого сценария нужно посчитать минимальные вознаграждения героев, чтобы они смогли попасть в кино.
Между двумя произвольными городами существует только одна дорога, по которой между ними можно проехать. Расстояние между любыми двумя соседними городами (между которыми существует прямая дорога) составляет $1$ километр. Столица всегда имеет номер $1$.
\InputFile
В первой строке находится два натуральных числа: количество городов $n\:(1 \le n \le 10^5)$ в iLandia, и цена $Price\:(1 \le Price \le 10^4)$ за $1$ км в стране. Каждая из следующих $n - 1$ строк содержит два натуральных числа $x$ и $y\:(1 \le x, y \le n)$, описывающих наличие дороги из города $x$ в город $y$. Все дороги двухсторонние. В следующей строке задается количество сценариев $q\:(1 \le q \le 10^5)$. Каждый сценарий начинается с новой строки и задаётся номерами городов $c$ и $d\:(1 \le c, d \le n)$, в которых заканчивают свои приключения соответственно Чип и Дейл.
\OutputFile
Выведите два числа: затраты Чипа и Дейла на дорогу с точностью не менее $10^{-5}$.
Входные данные #1
3 2 1 2 1 3 3 2 3 1 2 1 3
Выходные данные #1
2.00000 2.00000 0.00000 2.00000 0.00000 2.00000