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

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

I didn't understand what paint(v) means. Can someone please explain me. Also I didn't understand the editorial solution of this problem. Can't we just count unconnected black ans white components and output min of them Problem link Thanks in advance!

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

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

paint(v) means that you should choose a vertex (v) and color all vertices (u) which have the same color as (v) and at the same time there is no vertex that has another color in the simple path between (v) and (u).

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

Your solution which is counting unconnected black and white components and output the minimum of them should be true.

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

The editorial is just explaining how you can count those unconnected black and white components in an efficent way (compressing the tree and finding the diameter).