Hi, Can Anyone explain the approach for the problem Link: GREEDYCH Problem - CodeChef

Please suggest some good tutorial on dynamic programming on trees. Also some problems on the same

Thanks in advance.

Hi, Can Anyone explain the approach for the problem Link: GREEDYCH Problem - CodeChef

Please suggest some good tutorial on dynamic programming on trees. Also some problems on the same

Thanks in advance.

its giving 404 error on clicking the linkâ€¦

yeah sorry link got expired , Now Updated please reply.

Its a basic tree dp problem. Like for each node letssay we have two dpâ€™s

Lets root the tree at 1

dp1[vertex][i] = denote largest sum path(bamboo) which ends in vertex or some child of vertex or child of childâ€¦ such that ,that path is increasing ,and last value of node in that path is i

Similarly

dp2[vertex][i] denotes path(bamboo) for decreasing sequence which starts at vertex or some child of vertex (and goes down)

Now just mergisng is left

Ans[vert] is nothing but taking dp1[child1][i] and dp2[child2][j] j>i

U could see my solution in that sucessful submissionâ€¦

But i prefer that first practice dp on tree sums first,so that it would be easyfor u to understand,search on cf for the questiond.

1 Like