vinu_93's blog

1325C
By vinu_93, history, 6 years ago, In English

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

can someone help me please

  • Vote: I like it
  • -19
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
6 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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.

→ Reply