You have a root tree containing n vertexes. Let’s number the tree vertexes with integers from 1 to n. The tree root is in the vertex 1.
Each vertex (except fot the tree root) v has a direct ancestor p v. Also each vertex v has its integer value s v.
Your task is to perform following queries:
- P v u ( u ≠ v). If u isn’t in subtree of v, you must perform the assignment p v = u. Otherwise you must perform assignment p u = v. Note that after this query the graph continues to be a tree consisting of n vertexes.
- V v t. Perform assignment s v = t.
Your task is following. Before starting performing queries and after each query you have to calculate expected value written on the lowest common ancestor of two equiprobably selected vertices i and j. Here lowest common ancestor of i and j is the deepest vertex that lies on the both of the path from the root to vertex i and the path from the root to vertex j. Please note that the vertices i and j can be the same (in this case their lowest common ancestor coincides with them).
Input
The first line of the input contains integer n (2 ≤ n ≤ 5·104) — the number of the tree vertexes.
The second line contains n - 1 integer p 2, p 3, …, p n (1 ≤ p i ≤ n) — the description of the tree edges. It is guaranteed that those numbers form a tree.
The third line contains n integers — s 1, s 2, … s n (0 ≤ s i ≤ 106) — the values written on each vertex of the tree.
The next line contains integer q (1 ≤ q ≤ 5·104) — the number of queries. Each of the following q lines contains the description of the query in the format described in the statement. It is guaranteed that query arguments u and v lie between 1 and n. It is guaranteed that argument t in the queries of type V meets limits 0 ≤ t ≤ 106.
Output
Print q + 1 number — the corresponding expected values. Your answer will be considered correct if its absolute or relative error doesn’t exceed 10 - 9.
Examples
input
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
output
1.640000000
1.800000000
2.280000000
2.320000000
2.800000000
1.840000000
Note
Note that in the query P v u if u lies in subtree of v you must perform assignment p u = v. An example of such case is the last query in the sample.
Solution:
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
using namespace std;
const int N = 200010;
const int BLOCK = 350;
vector <int> g[N];
int pv[N];
int value[N];
long long coeff[N];
bool imp[N];
int down[N];
long long change[N], total[N];
int up[N];
long long sz[N];
int depth[N];
long long ans;
void dfs(int v) {
coeff[v] = 0;
sz[v] = 1;
down[v] = -1;
int only = -1;
for (int j = 0; j < (int)g[v].size(); j++) {
int u = g[v][j];
depth[u] = depth[v] + 1;
dfs(u);
sz[v] += sz[u];
coeff[v] -= sz[u] * sz[u];
if (down[u] != -1) {
if (down[v] == -1) {
down[v] = down[u];
only = u;
} else {
imp[v] = true;
}
}
}
if (imp[v]) {
down[v] = v;
}
coeff[v] += sz[v] * sz[v];
ans += value[v] * coeff[v];
if (!imp[v] && only != -1) {
change[v] = (sz[v] + 1) * (sz[v] + 1) - sz[v] * sz[v];
change[v] -= (sz[only] + 1) * (sz[only] + 1) - sz[only] * sz[only];
change[v] *= value[v];
} else {
change[v] = 0;
}
}
char op[N];
int arg1[N], arg2[N];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
g[i].clear();
}
pv[1] = -1;
for (int i = 2; i <= n; i++) {
scanf("%d", pv + i);
g[pv[i]].push_back(i);
}
for (int i = 1; i <= n; i++) {
scanf("%d", value + i);
}
int tt;
scanf("%d", &tt);
for (int qq = 1; qq <= tt; qq++) {
char ch = getchar();
while (ch != 'P' && ch != 'V') {
ch = getchar();
}
op[qq] = ch;
scanf("%d %d", arg1 + qq, arg2 + qq);
}
int next_q = 1;
while (next_q <= tt) {
int last_q = next_q + BLOCK - 1;
if (last_q > tt) {
last_q = tt;
}
for (int i = 1; i <= n; i++) {
imp[i] = false;
}
for (int qq = next_q; qq <= last_q; qq++) {
if (op[qq] == 'P') {
imp[arg1[qq]] = true;
imp[arg2[qq]] = true;
} else {
imp[arg1[qq]] = true;
}
}
ans = 0;
depth[1] = 0;
dfs(1);
for (int i = 1; i <= n; i++) {
up[i] = i;
total[i] = 0;
}
for (int i = 1; i <= n; i++) {
if (down[i] != -1) {
total[down[i]] += change[i];
if (depth[i] < depth[up[down[i]]]) {
up[down[i]] = i;
}
}
}
if (next_q == 1) {
printf("%.15lf\n", (double)(1.0 * ans / n / n));
}
for (int qq = next_q; qq <= last_q; qq++) {
if (op[qq] == 'P') {
int v = arg1[qq];
int u = arg2[qq];
int z = u;
while (z != v && z != -1) {
z = pv[up[z]];
}
if (z == v) {
swap(u, v);
}
{
int z = v;
while (z != -1) {
ans -= total[z] * sz[v];
int new_z = pv[up[z]];
if (new_z == -1) {
break;
}
ans -= coeff[new_z] * value[new_z];
coeff[new_z] -= sz[new_z] * sz[new_z];
sz[new_z] -= sz[v];
coeff[new_z] += sz[new_z] * sz[new_z];
if (up[z] != z) {
coeff[new_z] += sz[up[z]] * sz[up[z]];
sz[up[z]] -= sz[v];
coeff[new_z] -= sz[up[z]] * sz[up[z]];
} else {
if (z != v) {
coeff[new_z] += (sz[up[z]] + sz[v]) * (sz[up[z]] + sz[v]);
coeff[new_z] -= sz[up[z]] * sz[up[z]];
} else {
coeff[new_z] += sz[up[z]] * sz[up[z]];
}
}
ans += coeff[new_z] * value[new_z];
z = new_z;
}
}
{
ans -= coeff[u] * value[u];
coeff[u] -= sz[u] * sz[u];
sz[u] += sz[v];
coeff[u] += sz[u] * sz[u];
coeff[u] -= sz[v] * sz[v];
ans += coeff[u] * value[u];
}
{
int z = u;
while (z != -1) {
ans += total[z] * sz[v];
int new_z = pv[up[z]];
if (new_z == -1) {
break;
}
ans -= coeff[new_z] * value[new_z];
coeff[new_z] -= sz[new_z] * sz[new_z];
sz[new_z] += sz[v];
coeff[new_z] += sz[new_z] * sz[new_z];
if (up[z] != z) {
coeff[new_z] += sz[up[z]] * sz[up[z]];
sz[up[z]] += sz[v];
coeff[new_z] -= sz[up[z]] * sz[up[z]];
} else {
coeff[new_z] += (sz[up[z]] - sz[v]) * (sz[up[z]] - sz[v]);
coeff[new_z] -= sz[up[z]] * sz[up[z]];
}
ans += coeff[new_z] * value[new_z];
z = new_z;
}
}
pv[v] = u;
total[v] = 0;
up[v] = v;
} else {
int v = arg1[qq];
ans += (arg2[qq] - value[v]) * coeff[v];
value[v] = arg2[qq];
}
printf("%.15lf\n", (double)(1.0 * ans / n / n));
}
for (int i = 1; i <= n; i++) {
g[i].clear();
}
for (int i = 2; i <= n; i++) {
g[pv[i]].push_back(i);
}
next_q = last_q + 1;
}
return 0;
}
