This longest path problem is solved in O(n) in competitive programmers handbook. I didn’t understand this. Can anybody help.
I don’t know how to print all longest path in O(N) time , , but yeah I can tell u longest path in tree in O(N) time … using BFS two times 
… if u want then i will explain
Thanks bro but i want to know the all longest paths in O(n) time. Read the pages I uploaded if you can understand.
Ok so i will do this first store all max lengths in distance array from a arbitary node (let say 1) …now in distance array find max values and insert their indices into vector (if there are multiple then insert them ) and for each value in vector i will call BFS and find max path…
any better approach @galencolin @waqar_ahmad224
Sorry I didn’t understand how will it find the longest path from every node and why will it work?
Refer to pic 2 -
when we call BFS from node 1 -
my distance array(means the distane between node 1 to node x) is (1 based indexing) -
0 1 1 1 2 2
so from node 1 the max distance is 2 which is for node number 5 and 6
now insert it in vector = {5,6}
Now assume 5 to be root node and find max distance 5->2->1->3 , 5->2->1->4 and for 6
6->2->1->3 , 6->2->1->4
1 Like
The approach used by the authors to find All longest paths in O(n) is called “Rerooting”.
Here are a few resources to begin with :
Video Explanation to All Longest Path in Tree by Rachit Jain
CF Blog
2 practice questions
6 Likes
ok ill try to explain, firstly the first O(n) run is going to be exactly like the diameter problem: you pick root arbitrarily and then you find the first and second max lengths from every node as you go down. After the first run you will have 2 max lengths but the problem we have now is that both these lengths go downward from any node. while the longest path could go upwards as well, therefore you run again in O(n) for a second time but this time around you store a third max which is the length you will get if you go up from a node x towards its parent p. also as root has no parent, you can store the roots third max length as 0. all the other nodes will have 3 max lengths out of which two go down towards its children (there could be any number of children, and one of these two paths ‘could’ correspond to one of the two paths that go downwards, in which case this downward path will be avoided, reason is in the book.). the third length is the length that goes up towards its parent. all comparisons in the nodes will compare all three paths and find longest. this comparison will take place before successive recursive calls.
i can write a code for you if its still not clear but id rather you try on your own first cuz i believe in you 
3 Likes