给定一棵有向树Ｔ，树Ｔ中每个顶点u都有一个权w(u)，树的每条边(u,v)也都有一个非负边长d(u,v)。有向树Ｔ的每个顶点u可以看做客户，其服务需求量为w(u)。每条边(u,v)的边长d(u,v)可以看做是运输费用。如果在顶点u处未设置服务机构，则将顶点u处的服务需求沿有向树的边（u,v)转移到顶点v处服务机构，则需付出的服务转移费用为w(u)*d(u,v)。树根处已设置了服务机构，现在要在树Ｔ中增设k处服务机构，使得整棵树Ｔ的服务转移费用最小。该算法对于给定的有向树Ｔ，计算在树Ｔ中增设k处服务机构的最小服务转移费用。