Notes 4: Codeforces 613D Div 1

This is my personal note and might be some kind of user editorial/learning material for some people!

This is the fourth episode of this "note" series. I will write notes on problems (normally around 2400-ish problems), which are solved without looking at the editorial, that are both interesting and educational. I normally will spend a few hours on each problem so please be patient when reading the blog. The problem on these notes should give a very interesting solution and will likely be optimizations problems (I feel like these problems have an IOI-style, which requires you to find some incomplete solution first then find the final solution using it).

If you want to motivate me to write a continuation (aka note 5), a significant upvote from you would be well appreciated! If I received lots of downvotes (because I'm also spending a lot of time to write this and to learn latex only to express my ideas accurately to you guys), I'm probably not gonna continuing writing these blogs.

Problem link

Problem statement:

Given a tree with NN nodes. You are given QQ queries. For each query, you are given an integer KK and an array aa of length KK.

We will color all these nodes in aa in red.

∑Qi=1Ki≤105,1≤N,Q≤105∑i=1QKi≤105,1≤N,Q≤105.

Enemies will try to disconnect these nodes by removing other nodes that are not in aa. Find minimum nodes (that are not in aa) removed in order to disconnect those nodes in aa. Queries are not permanent (the nodes destroyed will be resetted after the query).

Are you able to find the full solution from the hints?