Need Help ina SPOJ Problem

Thank You so much for your kindness and patience @everule1,bro i respect you

graph (4)
This is the same graph with weights. Here The longest pairwise distance is between 9 and 5.
d=1 and h=4;
My condition was that the second deepest node from 4, at a depth of 6, Is larger than d+ the distance of the furthest leaf from 1 in a different branch, which is 8, at a distance of 4. Now since 6>5, The flip happens at 4 instead of 1.Now since The second deepest node of 4 is further from 4 than the furthest node from 1 in a different branch+d. 5 is still one of the nodes in the longest pairwise path.

1 Like

You mean that two DFS will get me the answer always in this problem?

Can i get this through one DFS?

I don’t think that is possible.

through 2 its always possible?

1 Like

Cant we just simply start traversing through node 1 and apply DFS and the calculate Maximum?
Why are we taking only 2 largest depths.
Sorry @everule1,my doubt is silly

No, you don’t actually have to find those 2 nodes, You just have to find the one that’s furthest from 1. That’s a fact needed to prove the optimality of this method.

1 Like

And the number of DFS applied will depend on the no. of branches the tree have?
like in the test case of SPOJ the branch is 2

No, it’s only 2. Find furthest node from 1, and then find the furthest node from that node. That’s it.

Sorry,but is there a reason for it?Just clearing the residual doubt thanks

That was the point of the proof.

1 Like

Okay @everule1 Thank you so so so much for the illustrations and explainations.
I am glad that you helped me.
If i practice graph questions from A2OJ is that good?
can you suggest me any other platform for graphs

I can’t help you in finding questions. I don’t really do too many practice problems.

1 Like

Okay no problem. Thanks a lot for clearing my doubts now i have to just sit and grab what you told! if i have any further doubts i will text right here only…whenever you will be free please answer as per your convenience

THANKS!! @everule1