In today's Div.2E, I thought of a possible correct approach, but I can only feel that its number of operations is relatively good, and I can't calculate or give a hack.
My idea is that on a tree, we perform heavy chain decomposition on it. We found that the kangaroo needs to go through at most $$$log_n$$$ light edges to reach the root. For each heavy chain (a total of $$$log_n$$$), we perform binary division on it to the node of the next heavy chain. Then for this node (we assume it is $$$k$$$), for all its child nodes, we traverse from large to small according to the size of their subtrees, and this step only requires $$$O(\sqrt{siz_k})$$$.
I didn't elaborate on some of the small details, mainly because we need to prevent the kangaroo from running out of the subtree when we divide or query the child nodes, so we may query several times more (causing twice the constant).
Can anyone help me? Thank you very much.
Mole, not kangaroo.
Ur right XD
It got accepted. So wherein lies the problem?
I don't know that either, so I guess I need a hack or proof XD
Actually, I can`t understand your solution. But on my code, I used centroid so thought it would take logn querys too but it faild. so I add some more ideas. When I got right then remove all other paths from initial root that doesnt head toward centroid, And when I wrong, after remove subtree of centroid, move current root to its parent instead of perform one more query to check if mole escaped. Also remove all the leaf nodes cause mole moved. After perform these operations, my code accepted. I hope this help improving your code.
Thank you!
I had a recursive solution that’s very similar to yours. Initially, I find the heavy path from the root down to a leaf. I binary search over this path (making at most $$$2 \log{(path-length)}$$$ queries) to find the deepest vertex on the heavy path whose subtree contains the mole. Let’s call this vertex $$$v$$$. Then, I look through $$$v$$$’s children (the ones outside of the path), and find one whose subtree contains the mole (if it doesn’t exist, we’ll catch the mole at $$$v$$$). Once I find it, I recursively run the same algorithm on that subtree.
The key is to look through $$$v$$$’s children in decreasing order of subtree size, and, as you’ve mentioned, to make additional queries to ensure that the mole doesn’t leave $$$v$$$’s subtree. Now let’s bound the number of queries by a function of the current subtree size: $$$queries(m)$$$.
Initially, $$$m=n$$$. Binary search over the heavy path takes at most $$$2 \log{m}$$$ queries to find $$$v$$$. Now, suppose that, before finding the next subtree to explore, we’ve tried to check $$$k$$$ other children of $$$v$$$. Then, we would have made $$$2k+1$$$ queries before finding the right subtree, and the size of this subtree is at most $$$\frac{m}{k+2}$$$ (because the $$$k$$$ children before us have larger subtrees, plus the child on the heavy path).
Thus, we can bound the number of queries by: $$$2 \log{m} + 2k + 1 + queries(\frac{m}{k+2})$$$.
As you’ve mentioned, $$$k$$$ can only go up to $$$\sqrt{m}$$$ since otherwise the mole will escape the subtree of $$$v$$$. Hence, $$$queries(m) \leq \max_{k=0…\sqrt{m}}{(2 \log{m} + 2k + 1 + queries(\frac{m}{k+2}))}$$$.
If we compute the above relationship using DP, we get that $$$queries(5000) \leq 217$$$, meaning that our program will always make at most $$$217$$$ queries. This proves the solution for E1. This bound, though, is very loose, and it seems really difficult to construct a test case where anything close to it would be achieved. Perhaps tighter bounding would prove it for E2.
My solution for reference: 271646057
Yes, I think our solution is very similar, thanks for the proof XD