Consider the induced subgraph containing only stations whose teams have already been assigned. Since the original graph is a tree, its connected components can be maintained with a disjoint-set union structure. A path has no waiting team exactly when and belong to the same assigned-only component.
Represent every registered path by a forbidden edge between the current components of its endpoints. Assigning station merges with all already assigned neighboring components. A forbidden edge inside the set being merged means an old path would become empty. The new path is checked in the same way after the hypothetical merge.
Store the neighboring forbidden components for each component and merge smaller sets into larger sets. Testing plan before plan enforces the required priority.
Solution written by GPT5
