H. Подарок Санты
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Санты есть бесконечное число конфет каждого из $$$m$$$ вкусов. Вам дано корневое дерево с $$$n$$$ вершинами. Корень дерева — вершина с номером $$$1$$$. Каждая вершина содержит ровно одну конфету, $$$i$$$-я вершина содержит конфету вкуса $$$f_i$$$.

Иногда Санта боится, что конфеты вкуса $$$k$$$ испортились. Он выбирает любую вершину $$$x$$$ случайным образом и посылает поддерево вершины $$$x$$$ кондитерам на замену. Во время замены все конфеты вкуса $$$k$$$ в поддереве заменяются на новые конфеты того же вкуса, а конфеты не вкуса $$$k$$$ остаются неизменными. После замены дерево возвращается в состояние, в котором оно было до замены.

Настоящая цена замены одной конфеты вкуса $$$k$$$ равна $$$c_k$$$ (дана для каждого $$$k$$$). Однако, для простоты вычислений кондитеры берут за каждое посланное им поддерево одинаковую сумму $$$C$$$ вне зависимости от того, какое поддерево выбрано, сколько конфет в поддереве и какого вкуса они.

Предположим, что для заданного вкуса $$$k$$$ вероятность выбора каждой вершины Сантой для посылки на замену одинакова для всех вершин. Вам нужно найти математическое ожидание ошибки в подсчёте стоимости замены конфет вкуса $$$k$$$. Ошибка в подсчёте стоимости вычисляется так:

$$$$$$ Ошибка\ E(k) =\ (настоящая\ стоимость\ замены\ –\ цена,\ взятая\ кондитерами) ^ 2.$$$$$$

Обратите внимание, что настоящая стоимость замены равна стоимости замены одной конфеты вкуса $$$k$$$, умноженной на количество конфет этого вкуса в поддереве.

Иногда Санта заменяет конфету в вершине $$$x$$$ на конфету некоторого вкуса из его кармана.

Ваша программа должна уметь обрабатывать два типа запросов:

  • Изменить вкус конфеты в вершине $$$x$$$ на вкус $$$w$$$.
  • Подсчитайте математическое ожидание ошибки подсчёта стоимости замены конфет для заданного вкуса $$$k$$$.
Входные данные

Первая строка входных данных содержит четыре целых числа $$$n$$$ ($$$2 \leqslant n \leqslant 5 \cdot 10^4$$$), $$$m$$$, $$$q$$$, $$$C$$$ ($$$1 \leqslant m, q \leqslant 5 \cdot 10^4$$$, $$$0 \leqslant C \leqslant 10^6$$$) — число вершин в графе, количество различных вкусов конфет, число запросов и цена, которую кондитеры берут за замену поддерева? соответственно.

Вторая строка содержит $$$n$$$ целых чисел $$$f_1, f_2, \dots, f_n$$$ ($$$1 \leqslant f_i \leqslant m$$$), где $$$f_i$$$ — изначальный вкус конфеты в $$$i$$$-й вершине.

В третьей строке содержится $$$n - 1$$$ целое число $$$p_2, p_3, \dots, p_n$$$ ($$$1 \leqslant p_i \leqslant n$$$), где $$$p_i$$$ — родитель $$$i$$$-й вершины.

Следующая строка содержит $$$m$$$ целых чисел $$$c_1, c_2, \dots c_m$$$ ($$$1 \leqslant c_i \leqslant 10^2$$$), где $$$c_i$$$ — стоимость замены одной конфеты со вкусом $$$i$$$.

Следующие $$$q$$$ строк описывают запросы. Каждая строка начинается с целого числа $$$t$$$ ($$$1 \leqslant t \leqslant 2$$$) — типа запроса.

Если $$$t = 1$$$, тогда эта строка описывает запрос первого типа. За ним следует два целых числа $$$x$$$ и $$$w$$$ ($$$1 \leqslant  x \leqslant  n$$$, $$$1 \leqslant  w \leqslant m$$$) — Санта заменяет конфету в вершине $$$x$$$ на конфету вкуса $$$w$$$.

Иначе, если $$$t = 2$$$, строка описывает запрос второго типа и после него следует целое число $$$k$$$ ($$$1 \leqslant k \leqslant m$$$) — выведите математическое ожидание ошибки в подсчёте стоимости замены конфет для данного вкуса $$$k$$$.

Вершины пронумерован с $$$1$$$ до $$$n$$$. Вершина $$$1$$$ является корнем.

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

Выведите ответ на каждый запрос второго типа в отдельной строке.

Ваш ответ будет принят, если его относительная или абсолютная погрешность не превышает $$$10^{-6}$$$.

Формально, пусть ваш ответ равен $$$a$$$, а ответ жюри равен $$$b$$$. Ваш ответ будет засчитан, если и только если $$$\frac{|a-b|}{max(1,b)}\leqslant 10^{-6}$$$.

Пример
Входные данные
3 5 5 7
3 1 4
1 1
73 1 48 85 89
2 1
2 3
1 2 3
2 1
2 3
Выходные данные
2920.333333333333
593.000000000000
49.000000000000
3217.000000000000
Примечание

Для $$$1$$$-го запроса ошибка в подсчёте стоимости замены для вкуса $$$1$$$ равна $$$66^2$$$, $$$66^2$$$ и $$$(-7)^2$$$, если выбран $$$1$$$, $$$2$$$ и $$$3$$$ соответственно. Так как вероятность выбора каждой из вершин одинакова, математическое ожидание ошибки равно $$$\frac{66^2+66^2+(-7)^2}{3}$$$.

Аналогично, для $$$2$$$-го запроса ожидаемое значение ошибки равно $$$\frac{41^2+(-7)^2+(-7)^2}{3}$$$.

После $$$3$$$-го запроса, вкус конфеты на вершине $$$2$$$ изменится с $$$1$$$ на $$$3$$$.

Для $$$4$$$-го запроса ожидаемое значение ошибки равно $$$\frac{(-7)^2+(-7)^2+(-7)^2}{3}$$$.

Аналогично для $$$5$$$-го запроса ожидаемое значение ошибки равно $$$\frac{89^2+41^2+(-7)^2}{3}$$$.