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 ~N-1~ edges, where ~N~ 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 ~1~.

Let us consider just an ~a \leadsto b~ transfer. From the previous assertion it follows that the cheapest path from ~a~ to ~b~ will always be the shortest path from ~a~ to ~b~ – which is, in fact, the only path from ~a~ to ~b~ that does not have any repeated vertices. Borna's trip is thus uniquely defined by all of his stops. Getting from town ~a~ to town ~b~ requires that Borna first goes to the lowest common ancestor (LCA) node of ~a~ and ~b~, and then descends to ~b~ (note that the LCA can also be any of the nodes ~a~ and ~b~!). 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 ~\mathcal O(1)~ time.

Let us now define the notion of a banned (directed) edge: a directed edge ~a \to b~ is banned if it requires paying a bribe. If ~a~ is the parent of ~b~ for a banned edge ~a \to b~, then we call ~a \to b~ a down-banned edge. Similarly, we may define up-banned edges. If Borna traveled along a banned edge ~p~ times, then he will have to prepare ~1 + 2 + \dots + 2^{p-1} = 2^p-1~ 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 ~x~:

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

Now we consider the cases:

• If an edge ~a\to b~ is up-banned, then the number of times it was traversed is equal to the number of times any vertex in ~a~'s subtree was an initial stop, minus the number of times any vertex in ~a~'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 ~a\to b~ is down-banned, then the number of times it was traversed is equal to the number of times any vertex in ~b~'s subtree was a final stop, minus the number of times any vertex in ~b~'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 ~\mathcal O(N+K)~ time complexity, but even an ~\mathcal O(N \log N + K)~ approach is acceptable given these constraints.