Note that we really care about the number of times we need to traverse each of the roads. Once we know that, it is pretty easy to decide whether we will buy multiple single-pass tickets or a single multi-pass ticket.

In the first subtask, it was enough to use an algorithm like BFS or DFS to find a path between ~X~ and ~X+1~ while increasing the counter of traversals for each edge.

In the second subtask, our tree is actually a chain. Let's think about that chain as an array. Let's also keep around another array called ~dp~. Now, for every pair ~X~ and ~X+1~ we can increase ~dp[\min(pos[X], pos[X+1])]~ by ~1~ and decrease ~dp[\max(pos[X], pos[X+1])]~ by ~1~ where ~pos[x]~ denotes the position of node ~x~ in our chain. After we have done this for all neighbouring pairs, we can go over the ~dp~ array and add its elements into some variable ~cnt~. Note that in each moment of this traversal that variable holds the number of times we have traversed the corresponding edge in a chain.

To score all points we will slightly modify this algorithm to make it work on a tree. Let's root the tree in an arbitrary node. Let ~L~ be the lowest common ancestor of ~X~ and ~X+1~. Let's now increase ~dp[X]~ by ~1~, increase ~dp[X+1]~ by ~1~ and decrease ~dp[L]~ by ~2~. Now we can simply find out the number of traversals of each road by calculating the sum of ~dp~ values in a subtree of that road.

There is an alternative solution of the same time complexity which uses the so-called small-to-large trick. You can read about a very similar idea on this link.