Official

E - Unique Color Editorial by en_translator


This problem can be solved with DFS (Depth-First Search).

Prepare an array of “the number of vertices with each color on the path from vertex one to the current vertex,” and update it every time entering/exiting the vertex.

Each update of this array is done in an \(O(1)\) time, and with this array we can check if a vertex is good in an \(O(1)\) time, so the problem has been solved in a total of \(O(N)\) time.

posted:
last update: