Going to the movie#4463

Going to the movie (Editorial)

Since there is exactly one path between any pair of cities, the country’s road network forms a tree. To minimize their total expenses, it is advantageous for Chip and Dale to meet as early as possible. This happens if they meet at their lowest common ancestor, after which they can travel together by taxi to the capital, where the cinema is located.

Algorithm implementation

To find the lowest common ancestor (LCA), the binary lifting method is used. The graph is stored as an adjacency list in the array $g$ . The following global arrays are also declared for the LCA algorithm:

$d [v]$ — the time of entry into vertex $v$ during the depth-first search;
$f [v]$ — the time of exit from vertex $v$ during the depth-first search;
$d i s t [v]$ dist[v] — the distance from the root to vertex $v$ ;
$u p [v] [k]$ up[v][k] — stores the $2^{k}$ 2^k-th ancestor of vertex $v$ ;

#define MAX 100010
#define LOGMAX 18
vector<int> g[MAX];
int timer, d[MAX], f[MAX], dist[MAX];
int up[MAX][LOGMAX];

The dfs function performs a depth-first traversal of the tree starting from vertex $v$ . The vertex $p$ is the parent of vertex $v$ . The distance from the capital (vertex numbered $1$ ) to vertex $v$ is $l e n$ ; this value is stored in the array $d i s t [v]$ dist[v]. During the traversal, the entry and exit timestamps of the vertex are also computed — $d [v]$ и $f [v]$ .

void dfs (int v, int p = 1, int len = 0) 
{
  d[v] = timer++;

Store the immediate parent of vertex $v$ .

  up[v][0] = p;

Store the distance from the root (the capital) to vertex $v$ .

  dist[v] = len;

Build the table of binary ancestors.

  for (int i = 1; i <= l; i++)
    up[v][i] = up[up[v][i-1]][i-1];

From vertex $v$ , all possible transitions to adjacent vertices are considered. For each vertex $t o$ connected to $v$ by the tree edge $(v, t o)$ (v, to), the traversal proceeds to that vertex.

  for (int to : g[v])
    if (to != p) dfs (to, v, len + 1);
  f[v] = timer++;
}

The Parent function returns true if vertex $a$ is an ancestor of vertex $b$ .

int Parent(int a, int b)
{
  return (d[a] <= d[b]) && (f[a] >= f[b]);
}

The LCA function computes the lowest common ancestor (LCA) of two vertices $a$ and $b$ in the tree using the binary lifting method and the ancestor table $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++

The main part of the program. Read the input data.

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

Compute the value $l = ⌈ l o g_{2} n ⌉$ l = ⌈log_2n⌉.

l = 1;
while ((1 << l) <= n)  l++;

Build an undirected graph that, according to the problem statement, forms a tree.

for(i = 0; i < n - 1; i++)
{
  scanf("%d %d",&x,&y);
  g[x].push_back(y);
  g[y].push_back(x);
}

Run a depth-first search on the tree starting from the capital, where the cinema is located.

dfs(1);

Process the $q$ queries sequentially.

scanf("%d",&q);
for(i = 0; i < q; i++)
{
  scanf("%d %d",&x,&y);
  lca = LCA(x, y);

Before the meeting, Chip travels $d i s t [x] - d i s t [l c a]$ dist[x] - dist[lca] km, and Dale travels $d i s t [y] - d i s t [l c a]$ dist[y] - dist[lca] km. Together they travel exactly $d i s t [l c a]$ dist[lca] km by taxi.

  Chip = dist[x] - dist[lca];
  Deil = dist[y] - dist[lca];

Compute and print the final expenses.

  printf("%.5lf %.5lf\n", (Chip + dist[lca] / 2.0) * Price, 
          (Deil + dist[lca] / 2.0) * Price);
}