[Community Editorial] Codeforces Round #720 (Div.2) Problem D — Nastia Plays with a Tree

Revision en3, by lior5654, 2021-05-08 00:19:58

Hello Codeforces!

Today was Codeforces Round #720 (Div.2), in which I solved problem D — Nastia Plays with a Tree. As I find my solution different from the solutions I heard of after the contest, I will explain it in detail in this blog post. I will note that you still might find value in reading this if you solved the problem, as my proposed solution also maintains at every stage the graph being a forest (i.e I don't create any cycles).

I won't use spoiler tags as codeforces ruins them anyways after a few days :/

The Solution

Note that in this editorial, when I write simple path, I mean a simple path between two nodes without having extra edges going from any of the nodes that do not belong to that simple path, or simply a node not connected to anything (this will be clearer once we see drawings).

We should first note that bamboo is simply a tree that looks like a single line of connections (i.e a simple path).

We observe that given the sequence of moves the order we delete/link edges in does not change the resultant underlying graph. We consider the following question: how can we delete edges such that we can link the remaining forest via link operations to make a bamboo after we delete all of them?

Well, we want to achieve a simple path in the end, and a simple path can only be broken into nonintersecting simple paths, therefore after edge deletions, we should have a set of nonintersecting simple paths.

Now, our motivation is to take some pen & paper and draw how such a set looks like (not necessarily the optimal one) (in this editorial I cheat with CSAcademy Graph Editor). **Note that for convenience and as in many tree problems, we root the tree at an arbitrary node.

Suppose we are given the following tree (rooted at node 1):

We can convert it to a set of non-intersecting simple paths in multiple ways, one of which is deleting 4->10, 5->13 & 5->7, and if we were to apply this way we would end up with the following set of simple paths:

If we look at subtrees of the original tree and what they turned into after the deletion, we observe that if a node has outgoing edges to 2 of its original children from the original subtree then that node must not be connected to its parent.

This leads to an approach of dynamic programming over subtrees & an observation is that we can utilize the following state: whether or not our subtree root is connected to its parent. The motivation for this state is exactly what we state above, in order to connect to more than 1 child we must not be connected to our parent. Let sdp[c] be the minimum

Tags div2, 720, trees, dynamic programming

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en14 English lior5654 2021-05-08 01:45:27 6 Tiny change: ' and $d_1 <= 0$, then ' -> ' and $d_1 \le 0$, then '
en13 English lior5654 2021-05-08 01:39:37 66
en12 English lior5654 2021-05-08 01:35:40 1 Tiny change: 'O(n\log(n)$, depend' -> 'O(n\log(n))$, depend'
en11 English lior5654 2021-05-08 01:32:18 2386 (published)
en10 English lior5654 2021-05-08 01:12:51 184 Tiny change: 'f $d_0 \gr 0$, \n\n' -> 'f $d_0 \grt 0$, \n\n'
en9 English lior5654 2021-05-08 01:00:18 349 Tiny change: 'ly in $O(nlog(n))$ v' -> 'ly in $O(n*log(n))$ v'
en8 English lior5654 2021-05-08 00:54:59 49
en7 English lior5654 2021-05-08 00:53:35 14
en6 English lior5654 2021-05-08 00:52:54 1567
en5 English lior5654 2021-05-08 00:35:47 937
en4 English lior5654 2021-05-08 00:27:47 790
en3 English lior5654 2021-05-08 00:19:58 620 Tiny change: 'tQc.png)\n\n\n' -> 'tQc.png)\ntest\n\n'
en2 English lior5654 2021-05-08 00:07:09 1224
en1 English lior5654 2021-05-07 23:40:15 995 Initial revision (saved to drafts)