### mokoto's blog

By mokoto, history, 8 months ago, ,

in the problem sugarel and love , how to choose two sons such that we can maximize

DP[i][1]={max(DP[j][0]+v[i][j]+DP[t][0]+v[i][t])∣ where j and t are sons of i}. For all other sons, we add max(DP[j][0],DP[j][1],DP[j][2]) as given in editorial

since there can be nC2 choices time complexity would be O(n2) , how to do it in O(n) time .

i think we cant choose first two sums which gives max(DP[j][0]+v[i][j]+DP[t][0]+v[i][t]) as it will not always optimal .

any idea.

• 0

 » 8 months ago, # |   0 I was under the impression we choose the j with the largest DP[j][0]+v[i][j] and t with the second largest DP[t][0]+v[i][j] and that will maximise the sum.
•  » » 8 months ago, # ^ |   0 so what happened .. has it worked..
•  » » » 8 months ago, # ^ |   0 I finished coding it and it does not work. :(
•  » » » » 8 months ago, # ^ |   +3 i think this will work : first keep all the maxes i.e maxofall(dp[j][0] , dp[j][1] , dp[j][2])now also keep dp[j][0] + v[i][j] — max[dp[j][0] , dp[j][1] , dp[j][2] ) for all children of i . sort them and take the first two , and for rest take the maxe's .
•  » » » » » 8 months ago, # ^ |   0 Thanks that sounds like a good approach.
 » 8 months ago, # |   0 I thought of a very similar DP state, best(i, k) meaning "the best I can do from the subtree rooted at i using k edges to its sons"Clearly 0 ≤ k ≤ 2. If we call f(j) the maximum over k of best(j, k) for all j sons of i, then the sum over j of f(j) is best(i, 0)Now for k = 1, 2 think what terms you should take away from the sum and what you should add to that sum using 1 or 2 edges.Link to muy submission using this idea : https://csacademy.com/submission/2161792/
•  » » 8 months ago, # ^ |   0 thanks .