POJ 3013 - Big Chrismas Tree
Problem : A graph G, each edge has a value w[i], each vertice has a value v[i]. For a subtree T of G, the total value of T is sum_e(w[i]*sum_v(v[j])), where i is exist edge in T and j are all the vertices of decendants of i. Vertice 1 is always the root. The task is to find a tree to make value(T) minimum.
Solution : Transform the value: sum_e(w[i]*sum_v(v[j]))=sum_v(v[j]*sum_e(w[i])), where j is one of the vertice, and i is the edge in the path from 1 to j. Thus it can deep transform to sum_v(v[j]*dis[1, j]). Thus the answer is the smallest distance path tree start from 1.