У вас есть корневое неориентированное дерево, состоящее из 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 могут совпадать (в таком случае их наименьший общим предок совпадает с ними).
Выходные данные
Выведите q + 1 число — соответствующие математические ожидания. Ваш ответ будет считаться правильным, если абсолютная или относительная погрешность каждого числа не превышает 10 - 9.
Примечание
Обратите внимание, что в запросе P v u в случае, если u лежит в поддереве v, требуется присвоить pu = v. Пример такого случая — последний запрос в примере.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|