ELCA - VietMX's Blog

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·10⁴) — the number of the tree vertexes.

The second line contains n - 1 integer p ₂, p ₃, …, 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 ₁, s ₂, … s _n (0 ≤ s _i ≤ 10⁶) — the values written on each vertex of the tree.

The next line contains integer q (1 ≤ q ≤ 5·10⁴) — 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 ≤ 10⁶.

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

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;
}