hi,
given a tree with N nodes find the node such that its average total
distance from each other node is smallest
i.e. if nodes are labeled 0N-1 then
find i such that[ SUM d(i, j ){0=jN}] /N is minimum
NOTE: This is different from the classic problem of finding
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