# How to find all the edges shared by all diametral paths of a tree?

A diametral path in a graph is a shortest path whose length is equal to the diameter of the graph. Now, given a tree with $$n$$ nodes, I would like to find the set of edges (possibly empty) which are present in all diametral paths. Is there an efficient algorithm to do that?

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 (unique) 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.

An $$O(n^2)$$ algorithm is, for each edge, remove the edge and check the diameter of the tree (the forest now). If it did not change, then the edge is not in the set.
However, you can apply a greedy/dp trick for an $$O(n)$$ algorithm. First, root the tree at some vertex $$r$$. Hence, each vertex, except for $$r$$ gets a parent. You can then from the leaves up, find the distance from a vertex to the farthest leaf in its sub-tree. Actually, we will also keep the value of the longest path when the child having the current longest path is removed. After we compute all these values in a bottom-up manner, we go again top-down, computing for each vertex, the longest path from this vertex to a leaf not in its sub-tree. Now we can on $$O(deg(v))$$ compute for all edges incident to $$v$$ if there is a path of length equal to the maximum length and not using them.