algorithm - Distance of every possible path between all nodes in minimum spanning tree -

i want distance of nodes nodes. there few questions regarding none solves problem. appoach implementing recursive dfs , storing result of each path while backtracking problem having high running time , going through path n number of times (n being number of edges).

as can see in code running dfs every possible node root. dont know how reuse path know answer in 1 iteration of dfs search.

i think done in o(n) minimum spanning tree , there 1 path between pair of nodes.

my code :

vector<int> visited(50001); map< pair<ll,ll> , ll> mymap; map<ll, vector<ll> > graph;  void calc(ll start,ll node) {     visited[node]=1;     vector<ll>::iterator it;     (it = graph[node].begin(); != graph[node].end(); ++it)     {         if (!visited[*it])         {             ans+=mymap[make_pair(node,*it)];             mymap[make_pair(start,*it)]=ans;             calc(start, *it);             ans-=mymap[make_pair(node,*it)];         }     } } 

in main :

for(i=1;i<=n;i++)     {         fill(visited.begin(),visited.end(),0);         ans=0;         calc(i,i);     } 

i can think of solution of complexity o(n * logn) using divide , conquer. let me share it.

let's choose edge e of distance d connecting node a , b. let's cut it. have 2 tree root a , b. let's assume,

• number of nodes in tree a = na
• sum of distance between every node in tree a = ca
• sum of distance of every node root in tree a = ra
• number of nodes in tree b = nb
• sum of distance between every node in tree b = cb
• sum of distance of every node root in tree b = rb

so distance between every node in original tree is: ca + cb + (nb * ra + na * d * nb + na * rb))

now, can calculate sum of distance of every node in tree a or b using same approach. 1 thing careful that, have choose such edge e such difference between number of components isn't much. can find edge in tree if cut edge, difference between number of nodes in resulting 2 trees won't more 1.