← 返回题目列表

Codeforces · 1987/E

E. 很棒的树!

中文机器翻译题面 查看原题

给你一棵有 $$$n$$$ 个顶点的树,以顶点 $$$1$$$ 为根。第 $$$i$$$ 个顶点上写有一个整数 $$$a_i$$$。

令 $$$L$$$ 为 $$$v$$$ 的所有直接子节点 $$$^{\text{∗}}$$$ 的集合。如果对于所有顶点 $$$v$$$(其中 $$$L$$$ 不为空),$$$$$a_v \le \sum_{u \in L}{a_u}.$$$$$$ 在一次操作中,选择任何顶点 $$$v$$$ 并将 $$$a_v$$$ 增加 $$$1$$$,则称一棵树为精彩树。

找出使给定的树变得精彩所需的最少操作数!

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 $$$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$$$。

输出

对于每个测试用例,输出一个整数——使树变得精彩所需的最少操作数。

示例

输入 #1

4
5
9 3 4 1 2
1 1 3 3
2
5 3
1
2
36 54
1
3
0 0 0
1 2

输出 #1

3
2
0
0

注意

第一个测试用例中的树:

您可以在顶点 $$$5$$$ 上应用一次操作,在顶点 $$$2$$$ 上应用两次操作,以获得一棵美妙的树。

在第二个测试用例中,您可以在顶点 $$$2$$$ 上应用两次操作以获得一棵美妙的树。

在第三个和第四个测试用例中,树已经很好了,所以你不需要应用任何操作。