I knew I wasn’t the only one who thought of the problem like this! During the contest, I too was solving the obviously much more difficult task, and failed to come up with an algorithm that runs sufficiently fast.
The fastest runtime I came up with was O(K*N + N^2). This approach is easy: start with an edgeless graph, and for every ticket, run a BFS/DFS through the (original) tree and place directed edges from every node that you can reach with that ticket to that ticket’s starting node. After this it’s enough to run a Dijkstra to get the minimal distance from the root to every other node. Because there can be up to N^2 edges, the complexity is O(N^2).
Another useful observation for solving the problem better is that if you’re at node x and you just used an edge of ticket t to relax a node y, it’s useless to use anymore edges of ticket t, because they all lead to node y, and x is already the node with the least distance from root that is connected with y by an edge of ticket t. (Because of the order Dijkstra’s traverses the graph)
This means that each ticket will only actually need to be processed once, and then we can remove it from the set of unprocessed tickets. If you run a Dijkstra with a set, and manage to come up with a structure that supports the following operations:
- Query for any ticket in the structure that can reach our node x, or say that it doesn’t exist
- Remove ticket t from the structure
You can have a solution that runs in O(N log N + K * s), where s = operations per structure operation. Ideally s should be O(log N), but O(log^2 N) is okay too. Naively, this can be implemented in O(N) easily.
If you want, I can describe the pseudocode in more detail: I’m pretty sure it’s not wrong. But I don’t know how to code a data structure like this, or if it even exists. I had already tried writing the tree in the shape of an array, in many different ways, in order to maybe figure out how to build a segment tree on this aray, but failed. I’ve tried using centroid decomposition, but failed for the same reason I failed using HLD: a ticket can cover up to O(N) chains / centroid sectors, it doesn’t make sense to use these algorithms at all. I couldn’t think of a working BST either. Any help on the matter would be appreciated.