I came across this problem (DP on trees): http://acm.timus.ru/problem.aspx?space=1&num=1018 I solved some beginner level problems on DP but I can't get the logic of this particular topic. I tried reading about this topic on the IARCS website (link) but I couldn't understand it completely. Can anyone explain me DP on trees along with solving the question given above? (I mean, like a proper tutorial. Since there are very few good resources on DP on trees, it would help all of them searching for this topic) asked 07 Jan '15, 10:53

The first thing you need to understand is the question itself. I found its language a bit weird and that it interchanged a couple of terms, so I'll restate the question in purely technical terms (and hopefully not make a mess of it). Given a tree with n nodes and weighted edges rooted at node 1, find the maximum weight of a subtree rooted at 1 with exactly q edges. In other words, what they are calling branches are just edges. While performing dp on trees our state usually looks like dp(i,something) is the best we can do for the subtree rooted at i such that something is true. So, lets go with the most natural state we can think of, which is: let dp(i,j) be the maximum weight of a subtree rooted at i with exactly j edges. So, dp(i,0) will be 0 for all nodes since, a subtree with 0 branches will have 0 weight. For the leaves of the tree only dp(i,0) will exist since they don't have the option of having any more branches. The final result I want is dp(1,q). Now, lets take some arbitrary node v with children w1, w2 ..wm. (In this question there are always 2 children, but its better to understand the more general technique for m children) Now, if we are trying to find dp(v,3) i.e. the best subtree rooted at v with 3 edges then we have the following choices:
Note that when I said best possible subtree with 2 edges rooted at w1 that essentially means dp(w1,2). So our dp is starting to take shape in that it now depends on smaller subproblems, but it is still too tedious to actually compute all these cases. So we decide to process children in order and define a new dp, say, dp_v s.t. dp_v(i,j) is the best possible subtree rooted at v with j edges considering only the first i children of v. First we process w1: Every result after processing w1 will go into dp_v(1,j) since, we have just considered w1 i.e. the first child, so far. Since we are only considering w1 right now, the only way for v to have j edges in its subtree is to take edge 1 and then take (j1) edges from subtree at w1 in best possible way. Therefore, dp_v(1,j)=weight_of(edge 1) + dp(w1,j1) Now, we process w2: Every result we get now will be put into dp_v(2,j) since we will consider first 2 children (w1 and w2). So if we are calculating dp_v(2,j) then we have the following options:
dp_v(2,j)=max(dp_v(1,j) , dp_v(1,j(k+1)) + weight_of(edge 2) + dp(w2,k)) for all k After we process all m (in this question m=2 always) children of v we will then have dp_v(m,j) which is the best subtree rooted at v with j edges using its first m children, but since v has only m children, dp_v(m,j) is nothing but best subtree rooted at v with j edges considering all children, in other words dp_v(m,j) is the best subtree rooted at v with j children which is nothing but dp(v,j). I'll attach my code soon using the same terminology. Hope this helped. edit: I have not been very efficient in my solution as the aim was to illustrate dp on trees. One of the very easy ways to optimize this is to see that we do not need to declare a separate n x n dp_v for each node. Instead we can get away with a global 1D array of size n. answered 15 Jan '15, 18:14
