E. ELCA
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть корневое неориентированное дерево, состоящее из n вершин. Пронумеруем вершины дерева целыми числами от 1 до n. Корень дерева находится в вершине 1.

У каждой вершины (кроме корня дерева 1) есть непосредственный предок pv. Кроме того, в каждой вершине дерева v написано ее значение — целое число sv.

Необходимо последовательно обрабатывать следующие запросы:

  • P v u (u ≠ v). Если вершина u не лежит в поддереве v, необходимо присвоить pv = u. В противном случае, необходимо присвоить pu = v. Обратите внимание, после выполнения запроса граф всегда остается неориентированным деревом из n вершин.
  • V v t. Необходимо присвоить sv = t.

Ваша задача — до начала выполнения запросов, а также после выполнения каждого запроса выводить математическое ожидание значения, написанного на наименьшем общем предке двух равновероятно выбранных вершин i, j дерева. Под наименьшим общим предком вершин i и j понимается наиболее удалённая от корня вершина среди тех, которые лежат и на пути от корня до i, и на пути от корня до j. Обратите внимание, что i и j могут совпадать (в таком случае их наименьший общим предок совпадает с ними).

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

В первой строке входных данных записано целое число n (2 ≤ n ≤ 5·104) — количество вершин дерева.

Во второй строке записано n - 1 целое число p2, p3, ..., pn (1 ≤ pi ≤ n) — описание ребер дерева. Гарантируется, что данные числа задают дерево.

В третьей строке записано n целых чисел — s1, s2, ... sn (0 ≤ si ≤ 106) — значения, записанные изначально на каждой вершине дерева.

В следующей строке записано целое число q (1 ≤ q ≤ 5·104) — количество запросов. Каждая из следующих q строк содержит описание запроса аналогично тому, как они выглядят в условии задачи. Гарантируется, что параметры u и v запросов лежат в пределах от 1 до n. Гарантируется, что число t в запросах типа V удовлетворяет ограничениям 0 ≤ t ≤ 106.

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

Выведите q + 1 число — соответствующие математические ожидания. Ваш ответ будет считаться правильным, если абсолютная или относительная погрешность каждого числа не превышает 10 - 9.

Примеры
Входные данные
5
1 2 2 1
1 2 3 4 5
5
P 3 4
P 4 5
V 2 3
P 5 2
P 1 4
Выходные данные
1.640000000
1.800000000
2.280000000
2.320000000
2.800000000
1.840000000
Примечание

Обратите внимание, что в запросе P v u в случае, если u лежит в поддереве v, требуется присвоить pu = v. Пример такого случая — последний запрос в примере.