ENS1 - Editorial

1

Practice
Contest

Author: Soham Chakrabarti
Tester Arkapravo Ghosh
Editorialist: Soham Chakrabarti

DIFFICULTY :

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