Problem

The problem is about devising an optimal strategy, to minimize the diameter of a tree by removing at most K leaves.

One of the solution greedily removed one of the end node of the current diameter, If their are several choices then one of the leaf with maximum no. of diameter starting from it,is preferred)

Code

Can anybody explain me why this will always work..?

Thanks

I was trying to solve This problem of Google APC 2015.

I did a o(n^4) Dp for finding the maximum number of elements that can be removed, keeping the starting and ending index of the array(say i,j) and two loops for transition in a state for finding all possible triplets in i to j range.

Let (a,b,c) is a triplet possible such that b-a=c-b=k where i<=a<=b<=c<=j

dp[i][j]=max(dp[i][j],3+dp[i][a-1]+dp[a+1][b-1]+dp[b+1][c-1]+dp[c+1][j])

Can someone give a better complexity solution...

Thanks