## Editorial for Bubble Cup V8 B Bribes

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Let us first provide a suitable interpretation of the task description. The country can obviously be modelled as an undirected graph, where vertices are towns and edges are roads. We see that it is connected (the description mentions that every city is reachable), but we also know that there are edges, where is the number of vertices. From this it follows that the graph is, in fact, a tree. For the sake of simplicity, let us make this tree rooted at node .

Let us consider just an transfer. From the previous assertion it follows that the cheapest path from to will always be the shortest path from to – which is, in fact, the only path from to that does not have any repeated vertices. Borna's trip is thus uniquely defined by all of his stops. Getting from town to town requires that Borna first goes to the lowest common ancestor (LCA) node of and , and then descends to (note that the LCA can also be any of the nodes and !). Computing the LCA of two vertices is a well-known problem and may be solved in several different ways. One possible approach is to use the equivalence between LCA and the range minimum query (RMQ) problem and then compute the LCA of any two vertices in constant time. Another one is based on heavy path decomposition. In any case, we need to be able to compute the LCA in time.

Let us now define the notion of a **banned (directed) edge**: a directed edge is *banned* if it requires paying a bribe. If is the parent of for a banned edge , then we call a **down-banned edge**. Similarly, we may define **up-banned edges**. If Borna traveled along a banned edge times, then he will have to prepare thousands of dinars for bribing the police. Hence we need to determine the number of times every edge was traversed. This depends on whether the edge is down-banned or up-banned.

Before delving into these two cases, we need to compute the following three properties for every town :

*ends_down*: the number of times was the final stop in a path, this is equal to the number of occurrences of in the array of stops;*ends_up*: the number of times was the highest stop in a path, this is equal to the number of times was the LCA of two consecutive stops;*gone_up*: the number of times was the first stop in a path.

Now we consider the cases:

- If an edge is up-banned, then the number of times it was traversed is equal to the number of times any vertex in 's subtree was an initial stop, minus the number of times any vertex in 's subtree was the highest stop (i.e. sum of all
*gone_up*'s minus the sum of all*ends_up*'s). We may compute these parameters for all vertices at once using just one post-order tree traversal. Thus we can compute the 'bribe contributions' of all up-banned edges in linear time. - If an edge is down-banned, then the number of times it was traversed is equal to the number of times any vertex in 's subtree was a final stop, minus the number of times any vertex in 's subtree was the highest stop (i.e. sum of all
*ends_down*'s minus the sum of all*ends_up*'s). Similar to the previous case, we can compute the 'bribe contributions' of all down-banned edges using only one post-order tree traversal.

Hence, by first computing *ends_down*, *ends_up* and *gone_up* for every vertex, and then traversing the tree, we are able to compute the answer. The final complexity depends on the implementation of LCA. The asymptotically optimal solution to this problem has time complexity, but even an approach is acceptable given these constraints.

## Comments