do this way. start with any node(k) calculate sk = sum(k, i) for all i 0 <= i < n;
and u can easily get sj = sum(j,i) where j is adjacent to k; in O(n); suppose nj = number of nodes remains after removing edge(j,k) in subtree containing node j; suppose nk = number of nodes remains after removing edge(j,k) in subtree containing node k; sj = sk - nj * edgecost(j,k) + nk * edgecost(j,k); traverse the tree in bfs or dfs manner. maintain a minsum at every node compare it and modify accordingly. for ni (for all 0<=i < n) you have to preprocess the tree and u can get all in O(n); avgcost = minsum/n; -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
