题目大意 有一颗 nnn 个结点的树，定义一个结点的路径价值为 f(x)=∑i=1n(wi×d(x,i))f(x) = \sum_{i=1}^{n} (w_i \times d(x, i))f(x)=∑i=1n (wi ×d(x,i)) ，求整棵树的最小路径价值。 解题思路 考虑计算所有结点的路径价值，取最小值即可得到答案。 以上实现方法很容易想到换根DP，设 sumisum_isumi 表示子树 iii 的权值和，即 sumi=∑j=subtreei(wj)sum_i = \sum_{j=subtree_i} (w_j) sumi =j=subtreei ∑ (wj ) 并记录以 111 为根节点的路径价值 f(1)f(1)f(1) 。 接下来考虑换根，假设当前结点为 uuu ，父结点为 fafafa ，那么 f(u)=f(fa)+sum1−2×sumuf(u)=f(fa)+sum_1-2\times sum_uf(u)=f(fa)+sum1 −2×sumu 参考代码