SHADES - Editorial

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

Setter: Prasanna Kumar
Tester: Anshu Garg, Nishant Shah

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Euler Tour, Segment Trees

PROBLEM:

Given a rooted tree with N nodes. Initially, all nodes have colour black. You are also given Q queries of the following form:

  • Determine the number of paths passing through edge u\to v, with both endpoint nodes having the colour black.
  • Invert the colour of all nodes in the subtree of node u.

EXPLANATION:

graph (1)
(Leonardo gave the world ‘Mona Lisa’; here’s my masterpiece :stuck_out_tongue:)

Let b_1 and b_2 correspond to the number of black nodes in S_1 and S_2 (from above picture), respectively. For queries of type 1, the answer is equal to

b_1*b_2 \implies ((b_1+b_2)-b_2)*b_2

where b_1+b_2 is equivalent to the number of black nodes in the whole graph.

Thus we have reduced the problem to:

  • Invert the color of all nodes in the subtree of u
  • Determine the number of black nodes in the subtree of u (and subtree of node 1 - to find the total number of black nodes).

This can be solved efficiently using a Segment Tree (with lazy propagation) on the Euler Tour of the rooted tree.

How?

Run Euler Tour on the tree; let tin_u and tout_v be the entry and exit times of node u in the tour.

Consider an array A such that A_{tin_u} = 1 if node u is black. Initially, A_i = 1 for all valid i.

  • For a flip operation (query type 2) on the subtree of u, invert the value of all elements of A in the range [tin_u, tout_u].
  • To query the number of black nodes in the subtree of u, sum all elements of A in the range [tin_u, tout_u].

Both operations can be done in O(\log N) per query, using segment trees with lazy propagation.

TIME COMPLEXITY:

Running Euler Tour takes O(N). Building the segment tree takes O(N\log N). Each query takes O(\log N). The total complexity is thus:

O(N+N\log N+Q\log N) \approx O((N+Q)\log N)

SOLUTIONS:

Editorialist’s solution can be found here


Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

You mean bi*b2 = ((b1+b2)-b1)*b1

1 Like