一个树形DP的题目,求思路（最好详细点）或pascal程序FromAdmin☆建造城市背景Background清北学堂杯NOIP模拟赛第一道描述Description某城镇城市由n个村落{S1,S2,…,Sn}组成,且已建造n-1条道路

Question

一个树形DP的题目,求思路（最好详细点）或pascal程序
From Admin
☆建造城市
背景 Background
清北学堂杯NOIP模拟赛第一道
描述 Description
　　某城镇城市由n个村落{S1,S2,…,Sn }组成,且已建造n-1条道路证所有村落之间均有通路.市政府最近正在规划建立一座大型超市,其选址应尽可能缩短村民到该超市的距离.
　　这里,联接于村落S_i与村落S_j之间通路所经过道路的数目,即它们之间的距离,记作.
图1.城镇实例：dist(A,C) = 2,dist(A,D) = 3,dist(D,E) = 2
另外,鉴于各村落中居住人口的规模差异很大,因此在评估距离时还应顾及这一因素.于是,若用将村落Si 的人口规模记作|Si|,则选址于村落Sj的代价可表示为：cost(Sj)= ∑dist(Si,Sj)*|Si| (1

Answer 1

额 有点像“班级聚会”这题 貌似是SGU上的
不过这题是树形的 先DFS出每个节点的子树节点数 然后就应该可以转移了 LZ试试