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

1325C
Автор vinu_93, история, 5 лет назад, По-английски

i cant understand the problem. https://codeforces.net/problemset/problem/1325/C

can someone help me please

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

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

Solution

  • You have a tree with n vertices, so n-1 edges.
  • Mark all the edges with numbers from 0 to n-2.
  • Take any pair of vertices and write down the numbers on the edges in the shortest path between them.
  • Find the MEX of this array.

If you understand how MEX works, the problem is simple. The MEX of any path that doesn't contain the edge labeled 0 is 0. Find a vertex which has more than 3 edges, and mark them 0, 1, 2. Mark the remaining edges randomly. This ensures that the maximum MEX is 2.

→ Ответить