I finally got AC on problem G from Edu Round 98 earlier today. The editorial mentions centroid decomposition to get a runtime of $$$n \log^2 n$$$ or $$$n \log n$$$, but I actually had a completely different algorithm and I'm not 100% sure of the time complexity.

Like the editorial, my first idea was to compute the distances for each vertex to the closest of Bob's vertices using multi-source BFS. Then my goal is to iterate each vertex $$$v$$$, and for every vertex $$$u$$$ whose distance from $$$v$$$ is at most `bob_distance[v] - 1`

, update `answers[u]`

to be at least `bob_distance[v]`

.

Doing this directly via DFS is correct but obviously gets TLE, e.g., 99053280. I initially thought we could iterate $$$v$$$ in decreasing order of `bob_distance[v]`

and stop the DFS anytime we reach a node that already has an answer. But this is incorrect because there can be cases where a smaller distance node reaches farther in some direction than a larger distance node.

Instead, by adding a key optimization to track the `remaining`

steps we can still take from our current node and only continue the DFS when we strictly increase the maximum value of `remaining`

this node has seen, the algorithm is correct and gets AC: 99053359.

I suspect this algorithm is $$$n \sqrt n$$$ in runtime. (I have a specific case where it takes $$$n \sqrt n$$$ steps to finish). Can anyone prove this runtime as an upper bound?

I think I have a construction that requires $$$n^{5/3}$$$ steps. Here's a rough sketch.

Bob has a token at both B and B'. Then the $$$i$$$-th of the nodes on the right has

`bob_distance`

of $$$D-jk+2k-i$$$. This will update the A vertex with`remaining`

of $$$jk+2i-k$$$. The token at B' is just to ensure that these are the only updates that happen to A. Note this has size $$$O(D+k^2)$$$. If we duplicate this $$$k$$$ times for differentevenvalues of $$$j$$$, sharing the common A vertex, and add a bunch of leaves to A, this should force $$$Ω(n^{5/3})$$$ updates if we pick (roughly) $$$D=k^2=n^{2/3}$$$.I also think this example is tight. In an arbitrary tree, for each Bob token, the vertices that are closest to that token form a subtree, disjoint from the subtrees for the other tokens. Each subtree must have size $$$Ω(D+k^2)$$$ in order to trigger updates with $$$k$$$ distinct values for

`remaining`

at a given node, and with`bob_distance`

at least $$$D$$$, and the worst we can do is pick $$$D,k$$$ as above.Awesome! This might be the first time I've implemented something with $$$\displaystyle n^{\frac{5}{3}}$$$ runtime. Luckily the constant factor still seems good--I implemented your test case and it still runs well under the time limit.