Regarding a graph question on Prepbytes

Hi all,

I’ve been trying to understand a graph problem from prepbytes. Can any of you please help me on how to go about this?

Thank You!

P. S. - please try to overlook any mistakes, if any, in the submitted question; this is my first time asking here… :slight_smile:

Before solving you should be familiar with,
Euler Tour of a tree, and
Range query data structure(Segment Tree/BIT) depending on your preference.

  1. Lets root the tree at arbitrary index, lets say ‘1’.
  2. Now store prefix(i) denoting the number of captured provinces from path root node to i’th node.
  3. Also, use euler tour to linearize the tree into an array using dfs start and end times.
  4. Now the problem is converted into a simple point update and range query in a segment tree.

Make segment tree of prefix(i) array.
and its node in range [l:r] would denote the number summation of prefix from l to r.

How to handle updates?
Note that capturing/un-capturing a node will affect its subtree including the node.
That is in terms of of our dfs times, we have to update the range:
( start[node]:end[node] ) by +1 or -1 according to query.

You can learn Euler Tour from here and practice problems there Here

Hey thanks for the detailed reply! Umm i dont get what you mean by this -

Also, can you please explain a little bit on what is a minimum related subgraph?

prefix[node] = prefix[parent_node] + (captured[node] == 1? 1 : 0)

Its just count of the number of captured provinces from root to the current node, which we are traversing using dfs.

I think minimum related subgraph is just there to confuse you.