i recently recieved the same question with different contraints in a test and was unable to solve it in those constraints
You are given a tree consisting of vertices
You can perform the following operation at most times: delete a single leaf of the tree (the operation can produce new leafs, that can be deleted later). The resulting tree must have as small diameter as possible. Find the minimum possible diameter.
Input Format The first line contains two space separated integers n and k. Each of the next lines contains two space separated integers , describing the current tree edge. It's guaranteed that the given graph is a tree.
Constraints
0<n<=1e5
0<k<n
Sample Input #00
4 0
1 2
2 3
4 3
Sample Output #00
3
Sample Input #01
4 1
2 3
4 3
1 4
Sample Output #01
2
approach : i tried to find the distance of all leafs from center of diameter and made 3 vector left, right and center where left stored the distances of nodes left of center and right stored the distances of nodes right of center and center of all those nodes connected to center node which are part of center node forest.I was able to solve 52/60 test cased and hitted a block can someone help in this
I think you can solve it using BSTA (Binary Search on the Answer).
Let $$$d$$$ be the diameter we want to check.
If $$$d$$$ is even, we need to find a node $$$u$$$ such that "the number of nodes within distance $$$\displaystyle \leq \frac{d}{2}$$$ from $$$u$$$" is at least $$$n - k$$$.
If $$$d$$$ is odd, the idea is similar but a bit more complex. Instead of checking a single node $$$u$$$, we need to consider an edge $$$(u, v)$$$ and ensure that the combined number of nodes within distance $$$\displaystyle \leq \left\lfloor \frac{d}{2} \right\rfloor$$$ from both $$$u$$$ and $$$v$$$ is at least $$$n - k$$$.
To compute these distances, you can use re-rooting technique or other dynamic programming methods on trees.
The overall time complexity should be $$$O(n \log n)$$$.