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.
ok find diameter, take the mid node in it, now think of a branch going out of it with depth say 2 and the branches with the diameter end have depth >10. now think why will you even remove the leaves of the 2 depth branch at first