### FiveSixFiveFour's blog

By FiveSixFiveFour, history, 6 weeks ago,

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

The Solution

Solution By FiveSixFiveFour

This was very challenging to implement during the contest yet eventually I got AC 10 minutes before the end of the round. Thanks for the contest! :D

• +59

 » 6 weeks ago, # |   +8 Auto comment: topic has been updated by FiveSixFiveFour (previous revision, new revision, compare).
 » 6 weeks ago, # |   +11 Auto comment: topic has been updated by FiveSixFiveFour (previous revision, new revision, compare).
 » 6 weeks ago, # |   0 I will note here that my first idea was to simply guess that we should only keep a diameter and remove all other edges. I heard others in the community tries the same approach & failed. Here is a counterexample to that approach: The answer is 1, but the diameter idea will give an answer of 7.
•  » » 6 weeks ago, # ^ |   0 Don't remove all other edges. Recursively go to the child and find it's diameter too and attach one end of child diameter to it's parent's diameter.
•  » » » 6 weeks ago, # ^ |   +18 A better example of why recursively finding the diameter is not optimal isRecursively finding the diameter will cut 2 edges, but it is optimal to cut only edge 1-3
 » 6 weeks ago, # |   +8 Thank you for this editorial!