给你一棵有 $$$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$$$ 上应用两次操作以获得一棵美妙的树。
在第三个和第四个测试用例中,树已经很好了,所以你不需要应用任何操作。