REC25E - Editorial

editorial
, , ,
1

Contest

Author: Rick Sarkar
Tester: Abhishek Singh, Akshay A Baiju
Editorialist: Rick Sarkar

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

Dfs, HLD, Segment tree, Lazy Propagation

PROBLEM:

There are 3 type of queries.

  • In the first query you have to count the number of black and white nodes and repaint the path with the color having the maximum frequency. (If both have same frequency then do nothing).
  • In the second query you have to color the subtree with black.
  • In the third query you have to print the maximum value between the sum of white nodes and black nodes.

EXPLANATION:

Here we’ll be using the concept of HLD.

Let us denote color white as 0 and color black as 1.

So from this convention to calculate the total number of black nodes, we have to calculate the sum of the path between x and y.Now calculating the LCA of the nodes, we can get the total path distance.So,we have path distance and the number of black nodes.

The number of white nodes = path distance - Number of black nodes.

For the query of type 2, We’ll be adding the concept of Eular tour in our HLD.So that for each subtree update we know its in_time and out_time.

For the query of type 3, You can update the array of your decompossed tree up to your choice.In this part we’ll be updating the segment tree values as negative when we have to color it white and positive when we have to color it black.For the modify path sum value between the path x and y we’ll be getting all the black and white nodes together.

So for that, we’ll be having a segment tree made of the original values (positive values) and each query we get the path sum values in between the path of x and y.

Now in the path sum value we have all the positive values denoting all nodes as black and in the modify path sum value we have both black and white nodes.

From this to get the sum of values of black nodes and white nodes:

  1. ( path sum + modify path sum ) / 2 = all the black nodes
  2. ( path sum - modify path sum ) / 2 = all the white nodes.

TIME COMPLEXITY:

The time complexity for the problem is: O(n logn +q log^{2} n)

SOLUTIONS:

Setter's Solution

Problem_E_solution

Tester's Solution

Problem_E_tester_solution

Any other solution or feedback can be posted in the comments. We are always open to them.