CF1987E.Wonderful Tree!

神赐福于这个 ArrayForces！

一个随机的鹅卵石

给定一棵有 $n$ 个结点的树，根节点为 $1$。第 $i$ 个结点上写有一个整数 $a_i$。

设 $L$ 为结点 $v$ 的所有直接子节点的集合。若对于所有 $L$ 非空的结点 $v$，都有 $a_v \le \sum_{u \in L} a_u$，则称这棵树是“美妙的”。每次操作，你可以选择任意一个结点 $v$，将 $a_v$ 增加 $1$。

请你求出最少需要多少次操作，才能使给定的树变为美妙的。

$^{\text{∗}}$ 结点 $u$ 被称为结点 $v$ 的直接子节点，当且仅当：

• $u$ 和 $v$ 之间有一条边，并且
• $v$ 在从 $u$ 到树根的唯一路径上。

每组测试数据包含多组测试用例。输入的第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。

每组测试用例的第一行包含一个整数 $n$（$2 \le n \le 5000$），表示树的结点数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$），表示每个结点初始时写的值。

第三行包含 $n-1$ 个整数 $p_2, p_3, \ldots, p_n$（$1 \le p_i < i$），表示存在一条从结点 $p_i$ 到结点 $i$ 的边。保证给定的边能够构成一棵树。

保证所有测试用例中 $n$ 的总和不超过 $5000$。

对于每组测试用例，输出一个整数，表示将树变为美妙的最少操作次数。

第一个测试用例中的树结构如下：

你可以对结点 $5$ 操作一次，对结点 $2$ 操作两次，使得树变为美妙的。

在第二个测试用例中，你可以对结点 $2$ 操作两次，使得树变为美妙的。

在第三和第四个测试用例中，树本身已经是美妙的，因此不需要进行任何操作。

由 ChatGPT 4.1 翻译