D. Максимизация корня
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задано корневое дерево, состоящее из $$$n$$$ вершин. Вершины в дереве пронумерованы от $$$1$$$ до $$$n$$$, вершина $$$1$$$ — корень. Значение $$$a_i$$$ записано в $$$i$$$-й вершине.

Вы можете выполнять следующую операцию любое количество раз (возможно, ноль): выбрать вершину $$$v$$$, у которой есть хотя бы один сын; увеличить $$$a_v$$$ на $$$1$$$; и уменьшить $$$a_u$$$ на $$$1$$$ для всех вершин $$$u$$$, которые находятся в поддереве $$$v$$$ (за исключением самой $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальное возможное значение в корне, используя вышеописанную операцию.

Пример
Входные данные
3
4
0 1 0 2
1 1 3
2
3 0
1
5
2 5 3 9 6
3 1 5 2
Выходные данные
1
3
6
Примечание

В первом наборе входных данных возможна следующая последовательность операций:

  • провести операцию на $$$v=3$$$, тогда значения на вершинах станут $$$[0, 1, 1, 1]$$$;
  • провести операцию на $$$v=1$$$, тогда значения на вершинах станут $$$[1, 0, 0, 0]$$$.