Register | Login

Solutions of White path

Select solution language All Tiếng Việt English Other

Write solution here.

---

Jorge_Slime    Created at    0 likes

The approach involves performing a DFS starting from any node in the tree. During the traversal, a running count of white and black vertices is maintained. If a node is white (`0`), the counter increases by `+1`, and if it's black (`1`), the counter decreases by `-1`. This can be expressed as: ```cpp count += s[node - 1] == '0' ? 1 : -1; ``` As each node is visited, we check if the current count is positive. If it is, it means that along the path from the root to the current node, there are more white vertices than black ones, and this node qualifies. This method ensures efficient traversal in \( O(n) \), as each node is visited exactly once.