**Problem link** : contest practice

**Difficulty** : Medium Hard

**Pre-requisites** : Tree, Graph, LCA, Dynamic Programming, MST

**Problem** : There are N chambers. You can travel from any chamber A(x1, y1) to any chamber B(x2, y2) though the passage connecting them: It takes |x1 - x2| + |y1 - y2| minutes. There are Q queries of the form S_i, F_i. You have to print the minimal C such that for the path taken to reach from S to F, doesn’t have any edge greater than capacity C.

#### Explanation

One way is: do a single source shortest path algorithm from S_i(considering all N*N edges) and store the maximal number while doing the algorithm. This is not at all efficient.

It’s quite obvious, that if we will have a MST of the given graph, and then our problem will be reduced to just finding the maximal number written on an edge between S_i and F_i.

We have N*N edges, if we build the MST using all these edges, it won’t be efficient. We can do better.

We build the graph such that each point only connects to the nearest point from 8 directions. You can learn it in detail in ** Manhattan minimum spanning tree ** section on this page.

Now, how to handle queries? We can do a BFS/shortest path from S_i until we reach F_i and on the way we store the maximal number written on the edge. Still not efficient.

### Efficient and final solution

Let’s make our tree rooted with the root equal to 1. Then, let’s calculate F[i][j] that denotes 2^{j}-th ancestor of vertex i(just like we do, when we want to calculate LCA, link: [Another easy solution in [O(N logN, O(logN)]][133]). Then, we can calculate G[i][j] - the maximal edge between i and F[i][j]. So, we can calculate LCA of some pair (u, v), and at the same time calculate the maximal edge between those vertices. Read the tutorial on topcoder to get it more clear.

### Scoring

Here are the solutions that tester/setter had considered:

- Run a shortest path algorithm like [spfa][150] or Dijkstra at each query (15 points, subtask 1)
- Build the MST among all the N^2 edges and BFS at each query (15 points, subtask 1)
- Build the MST among all the N^2 edges and use the LCA algorithm to answer quries (30 points, subtask 1&2)
- Build the graph that each point only connects to the nearest point from 8 directions like the Manhattan minimum spanning tree algorithm do, and run a shortest path algorithm at each query(50 points, subtask1&3)
- Build the MST using the Manhattan minimum spanning tree algorithm, and BFS at each query(50 points, subtasks1&3)
- Build the MST using the Manhattan minimum spanning tree algorithm, and use the LCA algorithm to answer queries (100 points)

[133]:http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static#Another%20easy%20solution%20in%20O(N%20logN,%20O(logN)

[150]:http://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm