PROBLEM LINK:
Author: Tuấn Anh Trần Đặng
Tester: Kamil Dębowski
Editorialist: Tuấn Anh Trần Đặng
DIFFICULTY:
Hard
PREREQUISITES:
Graph, Dynamic Programming
Problem
Given a weighted vertex-catus of N vertices answer Q queries about the shortest path between a pair of arbitrary vertices u and v.
Assumptions
We will mainly work on the DFS tree of the catus eg. performing DFS from 1 and only take the edges that connect a vertex to the unvisited vertex during the process.
Sub-problem 1
Calculate the shortest path from 1 to every vertex u.
Solution
Let’s call this d[u]. We can get d by doing a dynamic programming in the DFS process. When we visit u there are two situations:
- u is not belong to any cycle: d[u] = d[parent[u]] + length of the edge from parent[u] to u.
- u is in a cycle C. In this case let top[C] is the vertex closest to the root in C. d[u] = d[top[C]] + shortest path from top[C] to u.
Note that there are exactly two ways to go between two vertices in the same cycle C so the shortest path from top[C] to u is just either the distance L from top[C] to u in the DFS tree or length of cycle C - L. top[C] should be pre calculated.
Sub-problem 2
Calculate the distance disTopDown(u, v) between u and one of it descendants v (in the DFS tree).
Solution
- If u is not belongs to any cycle then disTopDown(u, v) = d[v] - d[u]. This is correct since when we go from 1 to v we must go to u first.
- If u is belong to the cycle C. When go from 1 to v we may not go to u since we have two ways to pass through the cycle C. However we will have to go to the vertex b that is the vertex closest to v in C. We have that disTopDown(u, v) = d[v] - d[b] + shortest distance from b to u. Again since b and u are in the same cycle the distance between them can be easily calculated.
So it seems like our solution is quite obvious now: distance between two vertices u and v is disTopDown(lca(u, v), u) + disTopDown(lac(u, v), v) where lca(u, v) is the lowest common ancester of u and v in the DFS tree. But we still missing one more piece: how to find b. Let get to the final sub-problem.
Sub-problem 3
We will make the problem a bit more genernal. Given the cycle C and the vertex v find the first vertex of C in the path from v to the root of the DFS tree.
solution
Hint: we can use the similar technique that we used in finding LCA.
Order the cycle in the way that if cycle A lies on the path from root to cycle B then cycle A will get the larger order. One way is to use the order of the DFS completion of the top vertex eg. if the DFS process at top[B] finished later then B got larger order.
Now you may already guessed the solution. We trying to go from v toward the top as far as possible making sure that we never enter the cycle C. Let order[C] is the order of cycle C we have to make sure that the maximum order of cycles that has a vertex in the path from v toward the root does not larger or equal to order[C].
Recall the problem of finding LCA, we have to prepare f[u][i] is the 2^i th parent of u. The formular is quite simple:
- f[u][0] = parent[u]
- f[u][i] = f[f[u][i - 1]][i - 1]
Apply the same technique let maxOrder[u][i] is the maximum label from u to its 2^ith parent:
- maxOrder[u][0] = max(order[u], order[parent[u]]) where order[u] is the order of the cycle contain u or -1 if is does not belong to any cycle.
- maxOrder[u][i] = max(maxOrder[u][i - 1], maxOrder[f[u][i - 1]][i - 1]);
With maxOrder calculated we try to jump from v toward the root and makesure that we never go a vertex with a order larger than or equal to order[C]. If b exist it will be the parent of the vertex we ended up at since we tried to go as close to C as possible but never enter it.
Summary
The solutions contains three part:
- Initial DFS to prepare infomation of the cycles eg. top vertex, label …
- Second DFS to calculate d[] and maxLabel[][].
- Answer the queries: (distance from u to v) = disTopDown(lca(u, v), u) + disTopDown(lca(u, v), v);
Complexity: O((N + M)logN)