Ezvor

2445. Number of Nodes With Value One

MediumArray Preparing judge… LeetCode
ArrayTreeDepth-First SearchBreadth-First SearchBinary Tree

Hints

Hint 1
The relative order of processing queries does not matter.
Hint 2
If we know that for some node v, its parent was updated some number of times, then we know that node v was also updated that number of times.
Hint 3
Iterate on nodes from highest to lowest and count the number of times the query was performed on that node and the number of times this node was updated from its parent (direct or indirect). The parity of that number is the answer.