### PROBLEM LINK:

**Author:** Sergey Kulik

**Tester:** Jingbo Shang

**Editorialist:** Ajay K. Verma

### DIFFICULTY:

Medium-Hard

### PREREQUISITES:

### PROBLEM:

We are given a tree with edge weights belonging to {1, 2}. We need to handle the queries of the following form: given two nodes u and v in the tree, and and integer c, find the minimum number steps needed to reach from u to v, where in each step a maximum distance of c unit can be covered.

### EXPLANATION:

We divide the queries into two classes based on the value c. The queries for which c is smaller than N^{0.5} are kept in the first class, while the remaining queries are kept in the second class.

There is some common pre-processing that we need to do for the queries of both classes. Let us first discuss this pre-processing step.

First, we make the tree rooted, and maintain the following information for each node:

- distance of this node from root (stored in array dist[1…N])
- number of nodes in the path from root to this node (stored in array ht[1…N])
- 2
^{k}-th successor of this node, for all 0 <= k <= lg N (stored in array pt[1…N][0…lg N])

The three arrays can be computed easily using a depth first traversal of the tree.

void dfs(int u, int **adj, int **pt, int *dist, int *ht) { // special case for root if (pt[0] == -1) { dist = 0; ht = 0; } for (int v : adj) { if (v == pt[0]) continue; // update child's data dist[v] = dist + wt(u, v); ht[v] = 1 + ht; pt[v][0] = u; for (int i = 1 to lg N) pt[v]* = pt[v][i - 1] == -1 ? -1 : pt[pt[v][i - 1]][i - 1]; // recursion dfs(v, adj, pt, dist, ht); } }

Using the above information, the lowest common ancestor of two nodes u and v can be computed easily as shown below:

// Assumes that ht >= ht[v] int lca(int u, int v, int **pt, int *ht) { // Move from u to its ancestor, // until it is at the same level as v for (i = lg N to 0) { if (pt* == -1) continue; if (ht[pt*] >= ht[v]) u = pt*; } // At this point ht and ht[v] must be equal if (u == v) return u; // move simultaneously u and v towards root, // until they merge for (i = lg N to 0) { if (pt* != pt[v]*) { u = pt*; v = pt[v]*; } } return pt[0]; }

In order to handle the queries of first type, we need to some additional pre-processing, while the queries of the second class can be handled without any additional pre-processing.

Let us first discuss how to handle the queries of the second class.

##Queries with Large Value of c:

For the second kind of query, compute the lowest common ancestor w of nodes u and v, and then compute the number of steps to reach from u to w, and the number of steps to reach from v to w. This can be done using the pre-processed data computed in the previous section.

// returns the ancestor node of u that will be reached // in a single step from u. int single_jump(int u, int c, int *dist, int **pt) { int st = dist; for (int i = lg N to 0) { int v = pt*; if (st - dist[v] > c) continue; // move to v, if distance between u and v // does not exceed c u = v; } return u; } // moves up from u to w, returns the following two values: // 1) the number of steps taken to reach the closest // successor of w from u, such that the next step will take // us beyond w. // 2) the distance between w and this closest successor // of w. struct info { int num_steps; int dist_remaining; }; info move_up (int u, int w, int c, int **pt, int *dist, int *ht) { int num_steps = 0; int dist_remaining = 0; while (u != w) { // Use a single step int tmp = single_jump(u, c, dist, pt); if (ht[tmp] > ht[w]) { // we are still below w ++num_steps; u = tmp; } else { // we cannot take this step, otherwise // we will move beyond w dist_remaining = dist - dist[w]; break; } } return info{num_steps, dist_remaining}; }

Note that the complexity of single_jump is O (lg N), while the complexity of move_up depends on the number of steps taken to reach from u to w. Since the value of c is >= N^{0.5}, number of steps cannot be higher that N^{0.5}. Hence, the complexity of move_up is O (N^{0.5} lg N).

In a similar way, we can compute the number of steps taken to reach from v to w, and the remaining distance that we need to cover to reach w.

I1 = move_up(u, w, c, pt, dist, ht);

I2 = move_up(v, w, c, pt, dist, ht);

Now, we have taken (I1.num_steps + I2.num_steps) steps and we still need to cover (I1.dist_remaining + I2.dist_remaining) distance. This will require ceil ((I1.dist_remaining + I2.dist_remaining) / c) additional steps.

Hence, the queries of the second class can be handled in O (N^{0.5} lg N) time.

##Queries with Small Value of c:

Unfortunately, we cannot use the above approach for handling the queries of first class, as the number of steps to reach from u to w can be as large as O (N).

However, in this class there are only N^{0.5} distinct values of c, so we can do some preprocessing that can be used to process multiple jumps in O (1) time.

More formally for each value of c, we create an array P[1…N][0…lg N] such that P*[j] denote the ancestor node of i that can be reached after making 2^{j} jumps from i.

The array P[][] can be computed using a depth first traversal, in the same way as the array pt[][] was computed. Now using the array P, we can compute the number of steps to reach from u to w in O (lg N) time.

info move_up (int u, int w, int c, int **pt, int *dist, int *ht, int **P) { int num_steps = 0; for (int i = lg N to 0) { int tmp = P*; if (ht[tmp] > ht[w]) { // we are still below w num_steps += 2^i u = tmp; } } return info{num_steps, dist - dist[w]};

### Time Complexity:

Preprocessing time: O (N^{1.5} lg N)

Query time: O (N^{0.5} lg N)

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be put up soon.

Tester’s solution will be put up soon.