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.

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.

so what happened .. has it worked..

I finished coding it and it does not work. :(

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 .

Thanks that sounds like a good approach.

I thought of a very similar DP state,

best(i,k) meaning "the best I can do from the subtree rooted atiusingkedges to its sons"Clearly 0 ≤

k≤ 2. If we callf(j) the maximum overkofbest(j,k) for alljsons ofi, then the sum overjoff(j) isbest(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/

thanks .