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_distanceof $$$D-jk+2k-i$$$. This will update the A vertex withremainingof $$$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 different even values 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
remainingat a given node, and withbob_distanceat 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.