Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

VastoLorde95's blog

By VastoLorde95, history, 5 years ago, In English,

Hi, I am unable to understand the solution provided in the editorial of this problem. I read the explanations in the comments but can't seem to understand them either.

In the editorial dp max(v) is given as but in the sample solution 10973864 it is given as . How is that the same?

I have been at this for hours now! Can someone please help me? Thank you! :)

UPD - I have solved the problem using the method described here. But I would still like to know how the author's implementation is working since in the solution I implemented is different. In my submission, in one dfs we use the notation of dp(v) = k, being the k'th smallest value and in the other iteration as the k'th largest value, but in the author's solution, it seems to me that he has used the notation dp(v) = k as the k'th smallest value in both the cases. If so then can someone please clarify the transitions made by the author?

Tags 300, dp, tree
  • Vote: I like it
  • +6
  • Vote: I do not like it