4463. Going to the movie

 

Chip and Dale help all residents of the country iLandia. One day, after successfully completing their latest missions, they decided to go to the cinema. However, they were in for a surprise! There is only one cinema in the country, and it is located in the capital. Chip finished his adventure in city x, and Dale in city y.

There is very little time left before the movie starts, so both of them decided to order a taxi to arrive before the beginning of the film. Since the rewards of our heroes are rather small, each of them wants to keep their travel expenses as low as possible. Chip can join Dale in a taxi and vice versa if they happen to be in the same city. Since taxi drivers in iLandia charge a fixed price per kilometer, the cost of the part of the journey that the heroes travel together is split equally between them.

You are given several scenarios describing where Chip and Dale finish their adventures in different cities. For each scenario, determine the minimal expenses of the heroes so that they can get to the cinema.

Between any pair of cities there exists exactly one path along which it is possible to travel by car. The distance between any two neighboring cities (connected by a direct road) is 1 kilometer. The capital always has number 1.

 

Input. The first line contains two integers: the number of cities n (1 ≤ n ≤ 105) in the country iLandia and the price Price (1 ≤ Price ≤ 104) per 1 km of travel.

Each of the next n – 1   lines contains two integers x and y (1 ≤ x, y ≤ n) describing a road between cities x and y. All roads are bidirectional.

The next line contains the number of scenarios q (1 ≤ q ≤ 105).

Each of the following q scenarios is described by two integers c and d (1 ≤ c, d ≤ n) – the cities where Chip and Dale finish their adventures, respectively.

 

Output. For each scenario print two numbers – the expenses of Chip and Dale for traveling to the capital. The answers should be printed with precision of at least 10-5.

 

Sample input

Sample output

3 2

1 2

1 3

3

2 3

1 2

1 3

2 2

0 2

0 2

 

 

SOLUTION

data structures – Least Common Ancestor

 

Algorithm analysis

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;

·        dist[v] – the distance from the root to vertex v;

·        up[v][k] – stores the 2k-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 len; this value is stored in the array dist[v]. During the traversal, the entry and exit timestamps of the vertex are also computed – d[v] and 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 to connected to v by the tree edge (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 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];

}

 

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

 

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

 

Compute the value l = .

 

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 dist[x] – dist[lca] km, and Dale travels dist[y] – dist[lca] km. Together they travel exactly 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);

}