题目描述

给你一个有 n 个结点的二叉树的根结点 root=1 ，其中树中每个结点 node 都对应有 node.val 枚硬币。整棵树上一共有 n 枚硬币。

在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。移动可以是从父结点到子结点，或者从子结点移动到父结点。

输出使每个结点上 只有 一枚硬币所需的 最少 移动次数。

输入格式

第一行两个空格分开的整数分别表示 $n$ 和根结点上的硬币数量 $rootval$；

接下来 $n - 1$ 行，每行两个空格分开的整数分别表示编号 $i+1$ 结点的父亲结点编号和在这个结点上的硬币数量。

输出格式

一行一个整数表示答案。

示例 1：

3 3
1 0
1 0

2

解释: 一枚硬币从根结点移动到左子结点，一枚硬币从根结点移动到右子结点。

示例 2：

3 0
1 3
1 0

3

解释: 将两枚硬币从根结点的左子结点移动到根结点（两次移动）。然后，将一枚硬币从根结点移动到右子结点。

提示：

• 树中节点的数目为 n
• 1 <= n <= 100
• 0 <= Node.val <= n
• 所有 Node.val 的值之和是 n

SOURCE

在二叉树中分配硬币