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 -

  2. CP algo
  3. GFG

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.

can u please help @carre

please help @carre

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 ! :slight_smile:

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 :-




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 :slight_smile:

@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 :slight_smile:

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

Hello, @carre I am your fan ! :slight_smile:

I think you should fix that :grin: