Hello everyone. last week my teacher set's JOI18_bitaro as my homework (you can see the problem in here). I really tried to solve it and I spend many of hours thinking about it and finally I solved it. I didn't find any blog about its solution so I solve it in this blog.

I really appologize if this blog isn't good enough.

The main idea of this problem's solution looks too easy but actually it's difficult so don't be disappointed if you couldn't solve it.

At first we should solve the subtask 2 (really the first subtask isn't important) and then generalize it's solution for the subtask 3.

The subtask 2 is reaslly easy and we can solve it with only basic dp, but it don't work for subtask 3 because this dp solution takes O(m) time complexity and if q = 100000 then it will be time limit exceeded. Now note that sum of y of any query is not greater than 100000, so if y > sqrt(100000) we can handle the query by dp.

In this part of solving the problem we should just find a way to handle the queries with y less than sqrt(100000) and for doing this we can store a vector or array for any vertex and I name it lps (lengest paths).

Lps of v contains the first sqrt(100000) longest paths ending to v, I mean if for every vertex v we make a vector such that for vertex 1 ≤ u ≤ n, the longest path from u to v is in the lps of v and then we sort the elements in non increasing order and then we pop_back the vector while its size is greater that sqrt(100000).

After doing this we can handle the quries with y less than sqrt(100000), how? we go through the lps of t (vertex of party) and if any vertex in t's lps is removed (every query gives y vertices after giving t and y, I name them removed vertices) I mark it, then I find the maximum of not marked elements in lps of t and it's the answer of this query, why? we have sqrt(100000) vertex in lps of t and y is less that sqrt(100000) so there is at least one not marked vertex v in the t's lps and we know longest path of other vertices out of t's lps isn't greater that longest path of vertex v, so we if we find the maximum of not marked longest paths in t's lps, we found the answer. (if the size of t's lps is less that sqrt(100000) so we don't have sqrt(100000) vertex such that they have a path to t, so if all the vertices in the t's lps marked, the answer will be -1)

You can see my implemantation in here.

Thanks for reading my blog and sorry for my poor english.

I'm waiting to see your usefull comments to improve my next blogs.