# Get the treats - Hackerearth dfs problem

Here is the link to the problem

How can I solve these problem?

Hey , this is based on DFS , if u don’t know then please learn -

Also there is editorial section in the problem itself , go and check.

Thanks @ssrivastava990 for your response . I had tried doing it using dfs on every vertex which simply passes the test case and gives tle on remaining all other test cases , also the problem doesn’t have editorial.

obviously u did O(N2) so TLE.

yep DFS, it’s easier to write the code than to explain, I will try briefly
For each node find the 2 greatest paths from child_i to the corresponding leave and sum them; the answer is the maximum of that sums

[EDIT] ok, i see it’s not asking for the maximum but for each node, let me see

1 Like

This problem is a classical tree dynamic programming + re-rooting technique problem.

First, consider the root as “1” , simply calculate the best answer for root-‘1’ using dp.

Now apply re-rooting technqiue on this tree. And calculate answer for its children.

I have an idea but it’s not straightforward and it’s up to you to try it and figure out if it could work

1. for each node find the maxium 2 paths (p1 and p2) from it to a leave and call them s1[i] and s2[i]
2. the answer for the root is s1[root]+s2[root]+w[root]
3. the answer for a child of root is:
a) if child if in p1 or p2 then ans[child]=ans[root]
b) if child not in p1 and not in p2 then ans[child] = s1[child]+w[child] +p1[root] + w[root]
4. keep going down in tree and repeat the process

Hello, @carre I am your fan !

I think,

Only finding 1 best path (for each node) is sufficient because it is mentioned in the problem that once you start from a node, you can never go back.

So if edges are :-

1-2

1-3

1-4

For finding answer of root : Start from root, then go to either 2/3/4, only 1 way possible. Same is given in sample case.

Your solution solves a harder version of original problem.

To the op : Study tree dp + re-rooting technique properly to solve this problem

@carre,@i_code78 can u please provide some good resources to learn re-rooting technique?

Its mentioned in the codeforces blog you created 3-4 hours ago

Oh, yes! You are right I misunderstood completely the statement; @maverick06 please ignore what I said

Hello, @carre I am your fan !

I think you should fix that

2 Likes