Given a tree $T$ with $n$ vertices, we want to find the number of triplets of vertices $(a,b,c)$ such $d(a,b) = d(b,c) = d(c,a)$ where $d$ is the distance function (length of the shortest path between two nodes).It's pretty easy to do it in $O(n^3)$ time. Is it possible to do it faster?I think that on-line algorithm and pre-processing should help.
Find equidistant triplets in a tree
algorithms;graphs;dynamic programming;trees