 # ENS1 - Editorial

Author: Soham Chakrabarti
Tester Arkapravo Ghosh
Editorialist: Soham Chakrabarti

Medium

### PRE-REQUISITES :

Trees, Segment Trees, DFS

### PROBLEM EXPLANATION

Given a tree with N nodes and N-1 edges and provided with values in each and every node ( being only zero or one), you have to deal with Queries as followed:

1. swap the value of the node mentioned. ( 1 -> 0 and vice-versa).

2. Find the total number of set nodes below the Mth, where the Mth node lies in the path between the root node 1 and Uth node .

### SOLUTION

Pre process the tree by generating the three arrays.

• Count of total nodes below the Mth 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 Mth 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 Mth 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

3 Likes