Given a tree, I need to find all the edges that are shared by all diameters of that tree. In other words, let D be the length of the longest path in the tree and P be the set of all paths in the tree with length = D. I need to find the intersection of the edges shared by all paths in P. How can I do that? Please do not just mention the algorithm, I would appreciate if you can share the theoretical justification of why it works too (links to lectures or any resources are also very appreciated)↵
↵
I know how to do it in O(N^3) which is basically to iterate over all pairs of leaf nodes, check if their distance is equal to the diameter (this can be done using LCA) and if it is then traverse the path connecting them adding 1 to a counter associated to each edge along the way, and finally count how many edges have their counters equal to the number of diameters. This should work but it's quite expensive, and for sure there must be a more efficient approach.↵
↵
Thank you very much.↵
↵
Update: I need to know how to do this in order to solve this problem: https://www.codechef.com/MARCH13/problems/SUBTREE
↵
I know how to do it in O(N^3) which is basically to iterate over all pairs of leaf nodes, check if their distance is equal to the diameter (this can be done using LCA) and if it is then traverse the path connecting them adding 1 to a counter associated to each edge along the way, and finally count how many edges have their counters equal to the number of diameters. This should work but it's quite expensive, and for sure there must be a more efficient approach.↵
↵
Thank you very much.↵
↵
Update: I need to know how to do this in order to solve this problem: https://www.codechef.com/MARCH13/problems/SUBTREE
