func_code_string: #include <bits/stdc++.h>   using namespace std;   #pragma comment(linker,  /STACK:1024000000,1024000000 )   long long ans;   int son[100010][2], fa[100010], cnt[100010], val[100010];   int is[100010];   long long sumVal[100010], sumCnt[100010], sum[100010], all[100010],       lazy[100010];   void up(int p) {     sumCnt[p] = sumCnt[son[p][0]] + sumCnt[son[p][1]] + cnt[p];     sumVal[p] = sumVal[son[p][0]] + sumVal[son[p][1]] + val[p];     sum[p] = sum[son[p][0]] + sum[son[p][1]] + 1LL * cnt[p] * val[p];   }   void func(int p, long long v) {     if (!p) return;     all[p] += v * cnt[p];     lazy[p] += v;   }   void down(int p) {     if (lazy[p]) {       func(son[p][0], lazy[p]);       func(son[p][1], lazy[p]);       lazy[p] = 0;     }   }   void Rotate(int x) {     int y = fa[x], z = fa[y];     int o = son[y][0] == x;     down(y), down(x);     son[y][!o] = son[x][o], fa[son[x][o]] = y;     son[x][o] = y, fa[y] = x;     fa[x] = z;     if (is[y])       is[y] = 0, is[x] = 1;     else       son[z][son[z][1] == y] = x;     up(y);   }   void Splay(int x) {     int y, z;     down(x);     while (!is[x]) {       y = fa[x], z = fa[y];       if (is[y])         Rotate(x);       else if ((son[y][0] == x) ^ (son[z][0] == y))         Rotate(x), Rotate(x);       else         Rotate(y), Rotate(x);     }     up(x);   }   int Access(int x) {     int y = 0;     for (; x; x = fa[x]) {       Splay(x);       is[son[x][1]] = 1;       if (son[x][1]) {         cnt[x] += sumCnt[son[x][1]];       }       son[x][1] = y;       if (y) {         cnt[x] -= sumCnt[y];       }       is[y] = 0;       y = x;       up(x);     }     return y;   }   int vv[100010], nxt[100010], h[100010], e;   void add(int u, int v) { vv[e] = v, nxt[e] = h[u], h[u] = e++; }   void dfs(int u, int f) {     fa[u] = f, is[u] = 1, cnt[u] = 1;     son[u][0] = son[u][1] = 0;     all[u] = 1;     for (int i = h[u]; i + 1; i = nxt[i]) {       int v = vv[i];       dfs(v, u);       all[u] += 1LL * cnt[v] * cnt[u] * 2;       cnt[u] += cnt[v];     }     ans += all[u] * val[u];     up(u);   }   void change(int x, long long v) {     Splay(x);     ans += (v - val[x]) * all[x];     val[x] = v;     up(x);   }   int getFa(int x) {     Splay(x);     if (!son[x][0]) return fa[x];     int y = son[x][0];     while (son[y][1]) y = son[y][1];     return y;   }   void gao(int u, int v) {     Access(u);     Splay(v);     if (!fa[v]) swap(u, v);     int f = getFa(v);     if (f == u) return;     Access(f), Splay(f);     cnt[f] -= sumCnt[v], up(f);     fa[v] = 0;     ans -= 2 * sum[f] * sumCnt[v];     func(f, -2 * sumCnt[v]);     Access(u), Splay(u);     ans += 2 * sum[u] * sumCnt[v];     func(u, 2 * sumCnt[v]);     cnt[u] += sumCnt[v], up(u);     fa[v] = u;   }   int main() {     int n;     int u;     scanf( %d , &n);     memset(h, -1, sizeof(h)), e = 0;     for (int i = 2; i <= n; ++i) {       scanf( %d , &u);       add(u, i);     }     for (int i = 1; i <= n; ++i) scanf( %d , val + i);     dfs(1, 0);     int m, v;     scanf( %d , &m);     char c[3];     double mu = 1.0 * n * n;     printf( %.10lf n , ans / mu);     while (m--) {       scanf( %s%d%d , c, &u, &v);       if (c[0] ==  P )         gao(v, u);       else         change(u, v);       printf( %.10lf n , ans / mu);     }   }   