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 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/