Author: Soham Chakrabarti
Tester Arkapravo Ghosh
Editorialist: Soham Chakrabarti
DIFFICULTY :
Medium
PREREQUISITES :
Trees, Segment Trees, DFS
PROBLEM EXPLANATION
Given a tree with N nodes and N1 edges and provided with values in each and every node ( being only zero or one), you have to deal with Queries as followed:

swap the value of the node mentioned. ( 1 > 0 and viceversa).

Find the total number of set nodes below the M_{th}, where the M_{th} node lies in the path between the root node 1 and U_{th} node .
SOLUTION
Pre process the tree by generating the three arrays.

Count of total nodes below the M_{th} node.

DFS Traversal

Index of elements in the DFS traversal array
 After fetching all the data, build the segment tree, placing all the values of the nodes in the tree.
 For every Query, we input the M_{th} node to find the total set nodes below it (Excluding it).
 The left and right ranges will be defined as
L  index_in_DFS_traversal_array[M]+1
R  index_in_DFS_traversal_array[M]+subtree_size[M]1)
 For Swapping the value of the M_{th} node, we will pass the
index_in_DFS_traversal_array[M]
in our Update position parameter.
The rest remains the same as it happens in a segment tree.
Let us know your methods in the comment sections.
Setter’s solution : Can be found here