Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

Google Online Assesment question

Revision en1, by saazz, 2025-09-09 13:17:42

You are given a tree consisting of n vertices.

You can perform the following operation at most k times: delete a single leaf of the tree (the operation can produce new leaves, that can be deleted later). The resulting tree must have as small diameter as possible. Find the minimum possible diameter.

My Approach:- Delete all leaf nodes first until $$$k \gt =$$$ # of leaf nodes, Removing each layer will decrease diameter by 2 so let You can remove s layers then $$$D'$$$ = $$$D - 2*s$$$, Now the remaining k can decrease the diameter by 0 or 1, But i am stucked.

If you can solve this, plz explain.

Tags #trees

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English saazz 2025-09-09 13:17:42 625 Initial revision (published)