Get the treats - Hackerearth dfs problem

1

Here is the link to the problem

How can I solve these problem?

2

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

  1. CODEnCODE
  2. CP algo
  3. GFG

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

3

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.

4

obviously u did O(N2) so TLE.

5

can u please help @carre

6

please help @carre

7

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
9

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.

10

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
11

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

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

12

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

13

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

14

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:

2 Likes