We'll represent the network of cities and roads as a tree, rooted at an arbitrary node (node ~1~). Our overall approach will be to consider vehicle heights in decreasing order, in a line-sweep-like manner. Given the current vehicle height, we'll let ~Next[i]~ be the node to which vehicles of that height will drive to next from node ~i~ (equal to ~i~ itself if vehicles would remain there). Initially, for arbitrarily large vehicle heights, ~Next[i] = i~ for each ~i~ (as no roads can be used). As the vehicle height decreases, for each ~i~, ~Next[i]~ may increase as roads leading to higher-numbered cities become usable. For each node ~i~, if we sort its incident roads in non-increasing order of tunnel height (~\mathcal O(N \log N)~ time), we can precompute the sequence of vehicle heights at which ~Next[i]~ will increase (and what values it will increase to), each of which represents an event of interest in the overall line sweep. On top of these ~\mathcal O(N)~ events, we'll have ~K~ more events, one per moviegoer.

Assuming we maintain all nodes' ~Next~ values as we proceed through the line sweep, we'll have the appropriate values when processing each moviegoer ~i~, at which point we'll want to determine the final node they'll arrive at if repeatedly moving from their current node ~c~ (initially ~C_i~) to ~Next[c]~ (until ~Next[c] = c~). However, each moviegoer could perform ~\mathcal O(N)~ such moves, meaning that naive simulation yields a time complexity of ~\mathcal O(NK)~ and is too slow for full marks.

In order to optimize this approach, we'll begin by applying heavy-light decomposition to the tree. We'll still maintain the individual ~Next~ values of nodes not on heavy paths. However, for each heavy path, we'll instead maintain a set of intervals of contiguous subsequences of nodes along the path which all lead to a single node. For example, consider the following heavy path (with dashes representing currently-usable edges and underscores representing unusable ones): 1-3-5-2_7-4-6. It can be reduced into intervals: ~[1 \dots 2] \to 5~, ~[7 \dots 4] \to 7~, ~[6 \dots 6] \to 6~.

Each time a line sweep event causes a node's ~Next~ value to change, we can update the above representation as necessary in ~\mathcal O(\log N)~ time (with care taken when updating a heavy path's interval set to merge/split intervals appropriately). And each time we need to simulate a moviegoer's route, they'll only move along ~\mathcal O(\log N)~ heavy paths (each of which may be processed in ~\mathcal O(\log N)~ time) and ~\mathcal O(\log N)~ other nodes (each requiring ~\mathcal O(1)~ time), for a total of ~\mathcal O(\log^2 N)~. This brings us to an overall time complexity of ~\mathcal O(K \log^2 N + (N+K) \log(N+K))~.