4463. Поход в кино
Чип и Дейл
помогают всем жителям страны iLandia. Однажды, после успешного завершения
очередных миссий, они решили сходить в кино. Однако их ожидал сюрприз! В стране
есть всего один кинотеатр, и он находится в столице. Чип завершил своё
приключение в городе x, а Дейл – в
городе y.
До начала сеанса
осталось совсем немного времени, поэтому оба решили заказать такси, чтобы
успеть к началу фильма. Поскольку гонорары наших героев невелики, каждый из них
хочет потратить на поездку как можно меньше денег. Чип может подсесть в такси к
Дейлу и наоборот, если они окажутся в одном городе. Поскольку у таксистов
iLandia действует фиксированная цена за километр, стоимость участка пути,
который герои проехали вместе, делится между ними поровну.
Вам задано
несколько сценариев завершения приключений Чипа и Дейла в различных городах.
Для каждого сценария требуется определить минимальные расходы героев на поездку
в кино.
Между любой
парой городов существует ровно один путь, по которому можно проехать на
автомобиле. Расстояние между любыми двумя соседними городами (соединёнными
прямой дорогой) составляет 1 километр. Столица всегда имеет номер 1.
Вход. В первой строке заданы два натуральных числа: количество
городов n (1 ≤ n ≤ 105) в стране iLandia и
стоимость Price (1 ≤ Price ≤ 104) за 1 км поездки.
Каждая из
следующих n – 1 строк содержит два
натуральных числа x и y (1 ≤ x, y ≤ n), описывающих дорогу между городами x и y. Все дороги
двусторонние.
В следующей строке задано
количество сценариев q (1 ≤ q ≤ 105).
Каждый из следующих q сценариев задаётся двумя числами c и d (1 ≤ c, d
≤ n) – номерами городов, в которых Чип и
Дейл соответственно завершают свои приключения.
Выход. Для каждого сценария выведите два числа – расходы Чипа и Дейла на
дорогу до столицы. Ответы следует выводить с точностью не менее 10-5.
|
Пример
входа |
Пример
выхода |
|
3 2 1 2 1 3 3 2 3 1 2 1 3 |
2 2 0 2 0 2 |
РЕШЕНИЕ
структуры
данных – Least Common Ancestor
Анализ алгоритма
Поскольку между любой
парой городов существует ровно один путь, дорожная сеть страны образует дерево.
Чтобы минимизировать общие затраты, Чипу и Дейлу выгодно встретиться как можно
раньше. Это произойдет, если они встретятся в своем ближайшем общем предке,
после чего смогут вместе поехать на такси в столицу, где находится кинотеатр.
Реализация алгоритма
Для нахождения ближайшего
общего предка (LCA) используется метод двоичного подъема. Граф хранится в виде
списка смежности в массиве g. Также объявляются необходимые глобальные
массивы для работы алгоритма LCA:
·
d[v] – время входа в вершину v при поиске в
глубину;
·
f[v] – время выхода из вершины v при поиске в
глубину;
·
dist[v] – расстояние от корня до вершины v;
·
up[v][k] – хранит 2k-го предка вершины
v;
#define MAX 100010
#define LOGMAX 18
vector<int> g[MAX];
int timer, d[MAX], f[MAX], dist[MAX];
int up[MAX][LOGMAX];
Функция dfs выполняет
обход дерева в глубину, начиная с вершины v. Вершина p
является родителем вершины v. Расстояние от столицы (вершины с номером 1)
до вершины v равно len; это значение сохраняется в массиве dist[v].
В процессе обхода также вычисляются метки времени входа и выхода из вершины – d[v] и
f[v].
void dfs (int
v, int p = 1, int
len = 0)
{
d[v] = timer++;
Сохраняем непосредственного родителя
вершины v.
up[v][0] = p;
Сохраняем расстояние
от корня (столицы) до вершины v.
dist[v] = len;
Строим таблицу двоичных предков.
for (int i = 1; i <= l; i++)
up[v][i] = up[up[v][i-1]][i-1];
Из вершины v рассматриваются все возможные переходы
к соседним вершинам. Для каждой вершины to, соединённой с v
ребром дерева (v,
to), выполняется
переход.
for (int to : g[v])
if (to !=
p) dfs (to, v, len + 1);
f[v] = timer++;
}
Функция Parent
возвращает истину, если вершина a является предком вершины b.
int Parent(int
a,
int b)
{
return (d[a]
<= d[b]) && (f[a] >= f[b]);
}
Функция LCA вычисляет ближайшего общего предка (LCA) двух
вершин a и b в дереве с помощью метода двоичного подъёма и
таблицы предков up.
int LCA (int
a, int b)
{
if (Parent(a,
b)) return a;
if (Parent(b,
a)) return b;
for (int i = l; i >= 0; i--)
if
(!Parent(up[a][i], b)) a = up[a][i];
return
up[a][0];
}
Основная часть программы. Читаем
входные данные.
scanf("%d %d",&n,&Price);
Вычисляем значение l = 
.
l = 1;
while ((1 << l) <= n) l++;
Строим неориентированный граф,
который по условию задачи представляет собой дерево.
for(i = 0; i < n - 1; i++)
{
scanf("%d
%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
Запускаем на дереве поиск в глубину, начиная
со столицы, где находится кинотеатр.
dfs(1);
Последовательно обрабатываем q запрсов.
scanf("%d",&q);
for(i = 0; i < q; i++)
{
scanf("%d
%d",&x,&y);
lca = LCA(x, y);
До встречи Чип проедет dist[x] – dist[lca] км, а Дейл
dist[y] – dist[lca] км. Вместе на такси они проедут ровно dist[lca] км.
Chip = dist[x] - dist[lca];
Deil = dist[y] - dist[lca];
Вычисляем и выводим итоговые
расходы.
printf("%.5lf
%.5lf\n", (Chip + dist[lca] / 2.0) * Price,
(Deil + dist[lca] / 2.0) * Price);
}