Notes 4: Codeforces 613D Div 1

Правка en12, от NeoYL, 2023-12-26 20:25:34

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.

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

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.

Теги tree, dfs, virtual tree, implementation

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en18 Английский NeoYL 2023-12-31 12:32:49 185
en17 Английский NeoYL 2023-12-31 12:32:26 187
en16 Английский NeoYL 2023-12-31 12:30:21 58
en15 Английский NeoYL 2023-12-27 06:27:41 9 Tiny change: 'the large gap between n' -> 'the large time between n'
en14 Английский NeoYL 2023-12-27 06:07:00 112
en13 Английский NeoYL 2023-12-27 05:20:06 65
en12 Английский NeoYL 2023-12-26 20:25:34 12 Tiny change: '$ children? This mea' -> '$ children that is red? This mea'
en11 Английский 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 Английский NeoYL 2023-12-26 17:31:09 20
en9 Английский NeoYL 2023-12-26 15:22:09 253
en8 Английский NeoYL 2023-12-26 13:57:40 14 Tiny change: 'mary="Tags">\nHLD/b' -> 'mary="Tags/Prerequisites">\nHLD/b'
en7 Английский NeoYL 2023-12-26 12:49:08 6
en6 Английский NeoYL 2023-12-26 12:39:54 232
en5 Английский NeoYL 2023-12-26 12:37:31 16
en4 Английский NeoYL 2023-12-26 12:36:42 1 Tiny change: ' in $\{a\}) removed ' -> ' in $\{a\}$) removed '
en3 Английский NeoYL 2023-12-26 12:36:13 25 Tiny change: 'mum nodes removed i' -> 'mum nodes (that are not in $\{a\}) removed i'
en2 Английский NeoYL 2023-12-26 12:35:05 2 (published)
en1 Английский NeoYL 2023-12-26 12:34:21 7082 Initial revision (saved to drafts)