洛谷P2052题解

题目大意

给定一个$n$个点$n-1$条边的树,对于每一条边,代价为其权值乘其两端的点数之差的绝对值,求总代价。

分析

这道题其实很好想,对于每一条边,显然它的代价为其中一点的儿子数+1和其祖先数之差的绝对值乘权值。

那么我们只需要预处理求出每个点的儿子数,最后对于每一条边计算一下即可。

代码

为了保证网站的安全,特将代码从solution中将code分离。
Code : 戳我!!!!! (速度较慢,请耐心等待)