B. Ирис и дерево
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано корневое дерево с корнем в вершине $$$1$$$. Для любой вершины $$$i$$$ ($$$1 < i \leq n$$$) в дереве есть ребро, соединяющее вершины $$$i$$$ и $$$p_i$$$ ($$$1 \leq p_i < i$$$), вес которого равен $$$t_i$$$.

Ирис не знает значений $$$t_i$$$, но она знает, что $$$\displaystyle\sum_{i=2}^n t_i = w$$$ и любое из $$$t_i$$$ является неотрицательным целым числом.

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

Дерево на этой картинке удовлетворяет условию. Например, в поддереве вершины $$$2$$$ номера вершин равны $$$2, 3, 4, 5$$$, то есть являются последовательными целыми числами.
Дерево на этой картинке не удовлетворяет условию, так как в поддереве вершины $$$2$$$ номера вершин $$$2$$$ и $$$4$$$ не являются последовательными целыми числами.

Определим $$$\operatorname{dist}(u, v)$$$ как длину простого пути между вершинами $$$u$$$ и $$$v$$$ в дереве.

Далее произойдёт $$$n - 1$$$ событие:

  • Ирис сообщают целые числа $$$x$$$ и $$$y$$$, обозначающие, что $$$t_x = y$$$.

После каждого события Ирис хочет знать максимальное возможное значение $$$\operatorname{dist}(i, i \bmod n + 1)$$$ независимо для всех $$$i$$$ ($$$1\le i\le n$$$). Ей достаточно узнать только сумму этих $$$n$$$ значений. Пожалуйста, помогите Ирис быстро получить ответы.

Обратите внимание, что при вычислении максимально возможных значений $$$\operatorname{dist}(i, i \bmod n + 1)$$$ и $$$\operatorname{dist}(j, j \bmod n + 1)$$$ для $$$i \ne j$$$ неизвестные веса рёбер могут быть разными.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$w$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$0 \leq w \leq 10^{12}$$$) — количество вершин в дереве и сумма весов рёбер.

Вторая строка каждого набора входных данных содержит $$$n - 1$$$ целых чисел $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \leq p_i < i$$$) — описание рёбер дерева.

Затем следуют $$$n-1$$$ строк, обозначающих события. Каждая строка содержит два целых числа $$$x$$$ и $$$y$$$ ($$$2 \leq x \leq n$$$, $$$0 \leq y \leq w$$$), обозначающие, что $$$t_x = y$$$.

Гарантируется, что все $$$x$$$ в событиях различны. Также гарантируется, что сумма всех $$$y$$$ равна $$$w$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одну строку, содержащую $$$n-1$$$ целых числа, каждое из которых представляет ответ после каждого события.

Пример
Входные данные
4
2 1000000000000
1
2 1000000000000
4 9
1 1 1
2 2
4 4
3 3
6 100
1 2 3 2 1
6 17
3 32
2 4
4 26
5 21
10 511
1 2 2 4 2 1 1 8 8
3 2
6 16
10 256
9 128
2 1
5 8
8 64
4 4
7 32
Выходные данные
2000000000000
25 18 18
449 302 247 200 200
4585 4473 2681 1567 1454 1322 1094 1022 1022
Примечание

В первом наборе входных данных $$$\operatorname{dist}(1, 2) = \operatorname{dist}(2, 1) = t_2 = w = 10^{12}$$$, поэтому $$$\operatorname{dist}(1, 2) + \operatorname{dist}(2, 1) = 2 \cdot 10^{12}$$$

Во втором наборе входных данных дерево после того, как Ирис узнала все $$$t_x$$$, показано ниже:

$$$\operatorname{dist}(1, 2) = t_2$$$, $$$\operatorname{dist}(2, 3) = t_2 + t_3$$$, $$$\operatorname{dist}(3, 4) = t_3 + t_4$$$, $$$\operatorname{dist}(4, 1) = t_4$$$. После первого события мы узнали, что $$$t_2 = 2$$$, поэтому $$$\operatorname{dist}(1, 2) = 2$$$. В то же время:

  • $$$\operatorname{dist}(2, 3)$$$ максимально, если $$$t_3 = 7$$$, $$$t_4 = 0$$$. Тогда $$$\operatorname{dist}(2, 3) = 9$$$.
  • $$$\operatorname{dist}(3, 4)$$$ и $$$\operatorname{dist}(4, 1)$$$ максимальны, если $$$t_3 = 0$$$, $$$t_4 = 7$$$. Тогда $$$\operatorname{dist}(3, 4) = \operatorname{dist}(4, 1) = 7$$$.

Таким образом, ответ равен $$$2 + 9 + 7 + 7 = 25$$$.

После второго события мы узнали, что $$$t_4 = 4$$$, тогда $$$t_3 = w - t_2 - t_4 = 4$$$. $$$\operatorname{dist}(1, 2) = 2$$$, $$$\operatorname{dist}(2, 3) = 2 + 3 = 5$$$, $$$\operatorname{dist}(3, 4) = 3 + 4 = 7$$$, $$$\operatorname{dist}(4, 1) = 4$$$. Таким образом, ответ равен $$$2 + 5 + 7 + 4 = 18$$$.