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.
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