给你一棵有根树,由 $$$n$$$ 个顶点组成。树中的顶点编号从$$$1$$$到$$$n$$$,根是顶点$$$1$$$。值 $$$a_i$$$ 写入第 $$$i$$$ 个顶点。
您可以执行以下操作任意次数(可能为零):选择一个至少有一个子节点的顶点 $$$v$$$;将 $$$a_v$$$ 增加 $$$1$$$;并对 $$$v$$$ 子树中的所有顶点 $$$u$$$ 将 $$$a_u$$$ 减少 $$$1$$$($$$v$$$ 本身除外)。但是,每次操作后,所有顶点上的值都应该为非负数。
您的任务是使用上述操作计算写入根的最大可能值。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 树中的顶点数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) - 写入顶点的初始值。
第三行包含 $$$n-1$$$ 整数 $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i \le n$$$),其中 $$$p_i$$$ 是树中第 $$$i$$$ 顶点的父顶点。顶点 $$$1$$$ 是根。
对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 使用上述操作在根写入的最大可能值。
示例
输入 #1
3 4 0 1 0 2 1 1 3 2 3 0 1 5 2 5 3 9 6 3 1 5 2
输出 #1
1 3 6
注意
在第一个测试用例中,可以执行以下操作序列:
- 对$$$v=3$$$执行运算,则顶点上的值为$$$[0, 1, 1, 1]$$$;
- 对 $$$v=1$$$ 执行操作,则顶点上的值为 $$$[1, 0, 0, 0]$$$。