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.
It got accepted. So wherein lies the problem?