Loading repovive.com/contests/13/problems/F
| # | Title | Points | Solved | Admin | |
|---|---|---|---|---|---|
You are given a tree with vertices. The tree is rooted at vertex .
Each vertex is colored either blue or red. The color of vertex is denoted by .
For a vertex , consider the subtree of . For every integer , look at all vertices in this subtree whose distance from is exactly . Vertex is called good if, for every such , all these vertices have the same color. A level with zero or one vertex always satisfies this condition.
You have to process queries. In each query, one vertex is given and its color is toggled: blue becomes red, and red becomes blue.
After each query, output the number of good vertices in the tree.
For each test case, after each query output one integer, the number of good vertices after applying that query.
There is only one vertex, so it is good after every color change.
The tree is a path. For every vertex, each level inside its subtree contains at most one vertex, so all three vertices are always good.
After the first change, all children of vertex 1 have the same color, so every vertex is good. After each later change, the children of vertex 1 do not all have the same color, so vertex 1 is not good, while all leaves are good.
After the six changes, the sets of good vertices are respectively {4, 5, 6, 7, 8}, {2, 4, 5, 6, 7, 8}, {2, 3, 4, 5, 6, 7, 8}, {2, 4, 5, 6, 7, 8}, {2, 4, 5, 6, 7, 8}, and {2, 4, 5, 6, 7, 8}.
After the seven changes, the sets of good vertices are respectively {2, 3, 4, 5, 6, 7, 8, 9, 10}, {3, 5, 6, 7, 8, 9, 10}, {3, 5, 6, 7, 8, 9, 10}, {3, 5, 6, 7, 8, 9, 10}, {5, 6, 7, 8, 9, 10}, {5, 6, 7, 8, 9, 10}, and {5, 6, 7, 8, 9, 10}.