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]={max(DP[j]+v[i][j]+DP[t]+v[i][t])∣ where j and t are sons of i}. For all other sons, we add max(DP[j],DP[j],DP[j]) 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]+v[i][j]+DP[t]+v[i][t]) as it will not always optimal .

any idea. Comments (7)
 » I was under the impression we choose the j with the largest DP[j]+v[i][j] and t with the second largest DP[t]+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] , dp[j] , dp[j])now also keep dp[j] + v[i][j] — max[dp[j] , dp[j] , dp[j] ) 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 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/
•  » » thanks .