Help needed in approach for GREEDYCH

general
,
1

Hi, Can Anyone explain the approach for the problem Link: https://www.codechef.com/problems/GREEDYCH

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

Thanks in advance.

2

its giving 404 error on clicking the link…

3

yeah sorry link got expired , Now Updated please reply.

4

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…

5

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
6

@vivek_1998299 thanks