Subtask 1

For ~K = 0~, we can run a breadth first search for each squirrel to determine the length of its travel plan. The answer is the sum of the lengths.

For ~K = 1~, we can construct a new graph for each of the local roads combined with the highways. We can then run a breadth first search for each squirrel on the new graph to determine the minimum sum of lengths using one local road.

Time Complexity: ~\mathcal{O}(N \cdot M \cdot Q)~

Subtask 2

Since the graph is a cactus, each edge is only part of one cycle. It can be seen that the choice of whether or not to choose a local road does not affect the choices of whether or not to choose a different local road. In addition, we can see that each local road will decrease the sum of lengths by a fixed amount. Thus, we can use a greedy algorithm to pick the ~K~ local roads with the largest decreases. We can use an algorithm similar to subtask ~1~ and store the difference between the sum of lengths in the new graph and the sum of lengths in the tree. The sum of the ~K~ largest elements can then be found using a linear time selection algorithm (or with any standard sorting algorithm).

Time Complexity: ~\mathcal{O}(N \cdot M \cdot Q)~

Subtask 3

We can see that the shortest path between any two cities in the highway network plus one local road either passes through the local road or it does not. If it does not pass through the local road, then it must use only highways. We can precompute the length of the shortest path using only highways for each pair of cities by performing a breadth first search from each city. We can now get the distance between cities ~a_i~ and ~b_i~ in constant time. In the case where the shortest path passes through the local road, it must first pass through some (possible ~0~) highways, pass through the local road, and then through some more (possibly ~0~) highways. Thus, the shortest path between cities ~a_i~ and ~b_i~ using the ~j^{th}~ local road (between cities ~x_j~ and ~y_j~) is ~\min(\text{dist}(a_i, b_i), \text{dist}(a_i, x_j) + 1 + \text{dist}(y_j, b_i), \text{dist}(a_i, y_j) + 1 + \text{dist}(x_j, b_i))~ where ~\text{dist}(c, d)~ is the distance between cities ~c~ and ~d~ using only highways.

Time Complexity: ~\mathcal{O}(N^2 + M \cdot Q)~

Subtask 4

The greedy algorithm in subtask 2 can be similarly applied to subtask 3.

Time Complexity: ~\mathcal{O}(N^2 + M \cdot Q)~

Subtask 5

Instead of performing ~N~ breadth first searches to precompute ~\text{dist}(c, d)~ for all pairs of cities, we can instead use the fact that the distance between two vertices in a tree rooted at an arbitrary vertex is equal to ~\text{depth}(c) + \text{depth}(d) - 2 \cdot \text{depth}(\text{lca}(c, d))~. We can query for the lowest common ancestor (~\text{lca}~) in ~\mathcal{O}(1)~ time with ~\mathcal{O}(N)~ or ~\mathcal{O}(N \cdot \log N)~ precomputation using any data structure that supports range minimum queries over Euler tour indices.

Time Complexity: ~\mathcal{O}(N + M \cdot Q)~

Subtask 6

The greedy algorithm in subtask 2 can be similarly applied to subtask 6.

Time Complexity: ~\mathcal{O}(N + M \cdot Q)~

Subtask 7

If we arbitrarily root the tree of highways, we can observe that any path between two cities will first go up the tree, reaches the lowest common ancestor, and then go back down the tree. We can also see that for each cycle in the cactus graph, the cycle has a unique vertex that is closest to the root of the tree. We can call this vertex the root of the cycle. If we consider all vertices in a cycle, the local road will affect all travel plans passing through that vertex by a fixed amount. For each local road, we can compute this amount for each vertex in the cycle, and multiply it by the number of paths going through that vertex and up to the root of the cycle (which can be done using difference arrays). This amount will be added to the decrease in the sum of lengths for that local road. For cases where a path does not go through the root of the cycle (which means its lowest common ancestor is a non root vertex in the cycle), we can handle them each separately since this only happens at most once for each travel plan. We can see that the path in this case passes through some vertices not in the cycle, followed by some vertices in the cycle, and then finally some more vertices not in the cycle. The decrease in this case is equal to the minimum distance in the cycle between the first cycle vertex in the path, and the last cycle vertex in the path subtracted from the distance between those two vertices in the original tree. We can then choose the ~K~ best local roads similar to subtask 2.

Time Complexity: ~\mathcal{O}(N + M + Q)~