Похід в кіно#4463

Похід в кіно (Розбір)

Оскільки між будь-якою парою міст існує рівно один шлях, дорожня мережа країни утворює дерево. Щоб мінімізувати загальні витрати, Чіпу та Дейлу вигідно зустрітися якомога раніше. Це станеться, якщо вони зустрінуться у своєму найближчому спільному предку, після чого зможуть разом поїхати на таксі до столиці, де знаходиться кінотеатр.

Реалізація алгоритму

Для знаходження найближчого спільного предка (LCA) використовується метод двійкового підйому. Граф зберігається у вигляді списку суміжності в масиві $g$ . Також оголошуються необхідні глобальні масиви для роботи алгоритму LCA:

$d [v]$ — час входу у вершину $v$ при пошуку в глибину;
$f [v]$ — час виходу з вершини $v$ при пошуку в глибину;
$d i s t [v]$ dist[v] — відстань від кореня до вершини $v$ ;
$u p [v] [k]$ up[v][k] — зберігає $2^{k}$ 2^k-го предка вершини $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$ дорівнює $l e n$ ; це значення зберігається в масиві $d i s t [v]$ 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$ розглядаються всі можливі переходи до сусідніх вершин. Для кожної вершини $t o$ , з'єднаної з $v$ ребром дерева $(v, t o)$ (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$ у дереві за допомогою методу двійкового підйому та таблиці предків $u p$ .

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];
}

C++

Основна частина програми. Читаємо вхідні дані.

scanf("%d %d",&n,&Price);

Обчислюємо значення $l = ⌈ l o g_{2} n ⌉$ l = ⌈log_2n⌉.

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);

До зустрічі Чіп проїде $d i s t [x] - d i s t [l c a]$ dist[x] - dist[lca] км, а Дейл $d i s t [y] - d i s t [l c a]$ dist[y] - dist[lca] км. Разом на таксі вони проїдуть рівно $d i s t [l c a]$ 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);
}