You are not logged in. Please login at www.codechef.com to post your questions!

×

Can anyone teach me DP on trees with the help of solving this question?

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

ketanhwr's gravatar image

6★ketanhwr
1.9k31844
accept rate: 15%


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 sub-tree 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 sub-tree 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 sub-tree rooted at i with exactly j edges.

So, dp(i,0) will be 0 for all nodes since, a sub-tree 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)

blah

Now, if we are trying to find dp(v,3) i.e. the best sub-tree rooted at v with 3 edges then we have the following choices:

  1. Sub-tree rooted at v, takes edge 1, and then best possible sub-tree with 2 edges rooted at w1
  2. Sub-tree rooted at v, takes edge 2, and then best possible sub-tree with 2 edges rooted at w2
  3. Sub-tree rooted at v, takes edges 1&2, and then one edge from either sub-tree rooted at w1 or w2

Note that when I said best possible sub-tree 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 sub-problems, 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 sub-tree 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 (j-1) edges from sub-tree at w1 in best possible way.

Therefore, dp_v(1,j)=weight_of(edge 1) + dp(w1,j-1)

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:

  1. Don't take edge 2 at all, and take all j edges from previous children only
  2. Take edge 2 and some k more edges from sub-tree at w2 (total k+1 edges) and take the remaining j-(k+1) edges from previous children. Since the weight of optimally chosen k edges from sub-tree of w2 is nothing but dp(w2,k), we get the following relation:

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 sub-tree 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 sub-tree rooted at v with j edges considering all children, in other words dp_v(m,j) is the best sub-tree 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:

my solution

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 1-D array of size n.

link

answered 15 Jan '15, 18:14

akulsareen's gravatar image

4★akulsareen
47049
accept rate: 44%

edited 19 Jan '15, 06:33

Thanks a lot! :)

(16 Jan '15, 13:45) ketanhwr6★

Please attach your code fast.

(17 Jan '15, 13:33) ketanhwr6★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,966
×688
×48

question asked: 07 Jan '15, 10:53

question was seen: 32,632 times

last updated: 19 Jan '15, 06:33