Блог пользователя asdasdqwer

Автор asdasdqwer, история, 10 месяцев назад, По-английски

Hello,

could anyone please explain me the intuition behind the solution of CSES-Network Renovation?

The solution to the task

Why does this greedy strategy suffice for connecting the entire tree?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You can understand the intuition of the solution in intuition.

The gist of it is by adding k/2 we are guaranteed to have the nodes belong to different subtrees.

Hope this helps.