Part4.H - Martian Army

一道比较简单的树D，可以当作开胃菜。

题目大意

一颗树，根节点1的值为1.0，所有叶子节点的值为0.0，其他节点值任意。

我们要求所有相邻两个节点的值差的总和最小。输出这个总和。

解题思路

假设一个叶子节点为leaf，他的父节点为fa，leaf的祖父节点为g。

由定义得，那么leaf的值为0.0。

那么，此子树的最优结果为：

由于已经知道 ，我们贪心地想，假设祖父节点的值也已经确定，为 。为了使结果最优，应当满足条件 。这样一来，这棵子树取到最优答案 。

推广一下，如果儿子节点不是叶子节点呢？

很简单，我们扫遍fa的所有子节点，权值  保证 就可以了。

更新中。