← 返回题目列表

Codeforces · 1997/D

D. 最大化根

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

给你一棵有根树,由 $$$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]$$$。