Hints

• ||The constraints seem to imply that your solution should have complexity of ~O(n\times q)~, but the sum of the actual answer could be more than this. So we can't count pairs one-by-one.||
• ||We need to separate the tree into families of pairs, which all follow the same logic (or maybe worded differently, find families of paths where the edges replaced are the same, and so the impact on distance is the same)||
• ||If you compute the path between the two portals, edges introduced to existing paths will only include and remove a selection of these edges - why?||

Solution

View Solution

Suppose we have portals at ~a~ and ~b~, and we want to evaluate if ~x~ and ~y~ are now closer. Because the graph is a tree, the graph previously had 1 path between vertices - now it possibly has 2. If you play around with a few examples, you can find that if you draw the path from ~a~ to ~b~, there are two cases: 1. If the path from ~x~ to ~y~ has no edge intersects with the path from ~a~ to ~b~, then the distance is not shortened. 2. Otherwise, the path from ~x~ to ~y~ has one clear path intersect with the path from ~a~ to ~b~. Then we shorten the distance if the path intersect takes up more than half of the path from ~a~ to ~b~ (as then we can divert and use the opposite edges on the path to reach ~a~ and ~b~) As such, for any two pairs of nodes that would intersect the same points on the path from ~a~ to ~b~, the impact on the path would be the same. As such, we can do some aggregations by counting how many nodes appear in each subtree away from the point on the path, and then use any of these points interchangeably. If we still try every combination of subtree collections though, in the worst case this could stil lbe ~O(n^2)~ per query. Because our condition is rather simple (the nodes are from distinct subtrees that are more than (half the length of ~a \to b + 1~) apart), we can solve this with a prefix sum along the path, to calculate how many nodes are in any subtree at least a certain distance away! @code_include[solutions/main.cpp]{rm_config: True, langs: "cpp,py"}