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…
Before solving you should be familiar with,
Euler Tour of a tree, and
Range query data structure(Segment Tree/BIT) depending on your preference.
- Lets root the tree at arbitrary index, lets say ‘1’.
- Now store prefix(i) denoting the number of captured provinces from path root node to i’th node.
- Also, use euler tour to linearize the tree into an array using dfs start and end times.
- Now the problem is converted into a simple point update and range query in a segment tree.
How?
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?
Thanks!
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.