Thank You so much for your kindness and patience @everule1,bro i respect you
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.
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?
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.
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.
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.
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