  We present a polynomial time dynamic programming algorithm for optimal
partitions in the shortest path metric induced by a tree. This resolves, among
other things, the exact complexity status of the optimal partition problems in
one dimensional geometric metric settings. Our method of solution could be also
of independent interest in other applications. We discuss also an extension of
our method to the class of metrics induced by the bounded treewidth graphs.
