I randomly checked some of the code submissions for the last Div.3 G problem and found a lot of similar code.

292058768, 292001557, 292052679, 291997421

And I think there is a highly similar code 292026686.

I think I should mention some people.

MikeMirzayanov, cry

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.

My submission: E1: 271644722 My submission: E2: 271644923

Please note that the return value of the ceil function is not an integer, but a float / double / long double.

When you use cout output, your ceil may return a value of 8.49371e+06 instead of 8493712.

If you want to use its return value for output, you need to convert it to an integer first.

Yesterday, I encountered this problem while working on problem B of Codeforces Round 926 (Div. 2), and I took a penalty and searched for the error for a long time (246502057 and 246508172).

It's really bad.

I hope what I said is helpful to you, XD.