Editorial for Effortless

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.

1. 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"}