Notes 4: Codeforces 613D Div 1 [Hard]

Revision en18, by NeoYL, 2023-12-31 12:32:49

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), that are both interesting and educational. I normally will spend a few hours on each problem so please be patient when reading the blog.

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 $$$N$$$ nodes. You are given $$$Q$$$ queries. For each query, you are given an integer $$$K$$$ and an array $$${a}$$$ of length $$$K$$$.

We will color all these nodes in $$${a}$$$ in red.

$$$\sum_{i=1}^{Q}K_{i} \leq 10^5, 1 \leq N,Q\leq 10^5$$$.

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

Again, always try the problem before looking at the solution.

Tags/Prerequisites
Hint 1
Hint 2
Hint 3
Hint 4

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

Solution
Code
Feelings

Hope you guys learnt something from this blog.

Sorry for the large time between notes 3 and notes 4, I've been busy organizing a camp that is CP-related.

Tags tree, dfs, virtual tree, implementation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en18 English NeoYL 2023-12-31 12:32:49 185
en17 English NeoYL 2023-12-31 12:32:26 187
en16 English NeoYL 2023-12-31 12:30:21 58
en15 English NeoYL 2023-12-27 06:27:41 9 Tiny change: 'the large gap between n' -> 'the large time between n'
en14 English NeoYL 2023-12-27 06:07:00 112
en13 English NeoYL 2023-12-27 05:20:06 65
en12 English NeoYL 2023-12-26 20:25:34 12 Tiny change: '$ children? This mea' -> '$ children that is red? This mea'
en11 English NeoYL 2023-12-26 20:24:35 50 Tiny change: 'oiler>\n\n' -> 'oiler>\n\nHope you guys learnt something from this blog.\n\n'
en10 English NeoYL 2023-12-26 17:31:09 20
en9 English NeoYL 2023-12-26 15:22:09 253
en8 English NeoYL 2023-12-26 13:57:40 14 Tiny change: 'mary="Tags">\nHLD/b' -> 'mary="Tags/Prerequisites">\nHLD/b'
en7 English NeoYL 2023-12-26 12:49:08 6
en6 English NeoYL 2023-12-26 12:39:54 232
en5 English NeoYL 2023-12-26 12:37:31 16
en4 English NeoYL 2023-12-26 12:36:42 1 Tiny change: ' in $\{a\}) removed ' -> ' in $\{a\}$) removed '
en3 English NeoYL 2023-12-26 12:36:13 25 Tiny change: 'mum nodes removed i' -> 'mum nodes (that are not in $\{a\}) removed i'
en2 English NeoYL 2023-12-26 12:35:05 2 (published)
en1 English NeoYL 2023-12-26 12:34:21 7082 Initial revision (saved to drafts)