Check out this submission: 46652533.

The basic idea of this code is to find the diameter at first. Then, for each query, if the desire vertex can be on the diameter, we can find it in $$$O(1)$$$ time. Otherwise, we just jump up step by step, in this case the time complexity is $$$O(k)$$$.

Obviously, in the worst case the code runs in $$$O(n^2)$$$ time, but it got Accepted on Atcoder. It's even became the fastest solution among all submissions. All submissions

I have generated 3 pairs of test data to hack this. I constructed three chains with equal length and connected them with a center vertex, and then repeatedly generated queries on an endpoint with different $$$k$$$. Those 3 pairs of test data are using different strategy to generate $$$k$$$, which is showed in filenames. The data in on Google Drive.