B01T - Editorial

First we are using BFS to:

  1. Find and store parent of every vertex
  2. Store vertices in non-decreasing order of heights

Then we are calculating the prefix.

Then as per editorial, we are iterating through the vertices in order and when we find the required vertex, we mark all vertices after it, those are the vertices will be inverted. To invert a subtree, we only need to operate on its root. So we are doing operation on vertices which are marked but their parent is unmarked

1 Like