func_code_string: #include <bits/stdc++.h>   using namespace std;   const int N = 100005;   int n, m, x, y, f[N], fa[N], ch[N][2];   char op[5];   long long a[N], siz[N], ssiz[N], ans[N], sans[N], sqsiz[N], all[N];   bool isroot(int u) { return ch[fa[u]][0] != u && ch[fa[u]][1] != u; }   int which(int u) { return u == ch[fa[u]][1]; }   void pushup(int o) {     int lc = ch[o][0], rc = ch[o][1];     siz[o] = siz[lc] + siz[rc] + ssiz[o];     all[o] = all[lc] + all[rc] + a[o] * ssiz[o];     ans[o] = ans[lc] + ans[rc] + sans[o];     ans[o] += (ssiz[o] * ssiz[o] - sqsiz[o]) * a[o];     ans[o] += 2 * siz[rc] * ssiz[o] * a[o];     ans[o] += 2 * all[lc] * (siz[o] - siz[lc]);   }   void rotate(int x) {     int y = fa[x], z = fa[y], md = which(x);     if (!isroot(y)) {       ch[z][which(y)] = x;     }     fa[x] = z;     ch[y][md] = ch[x][!md];     fa[ch[y][md]] = y;     ch[x][!md] = y;     fa[y] = x;     pushup(y);     pushup(x);   }   void splay(int u) {     while (!isroot(u)) {       if (!isroot(fa[u])) {         rotate(which(u) == which(fa[u]) ? fa[u] : u);       }       rotate(u);     }   }   void access(int u) {     for (int v = 0; u; v = u, u = fa[u]) {       splay(u);       int rc = ch[u][1];       ssiz[u] += siz[rc];       sans[u] += ans[rc];       sqsiz[u] += siz[rc] * siz[rc];       ch[u][1] = v;       ssiz[u] -= siz[v];       sans[u] -= ans[v];       sqsiz[u] -= siz[v] * siz[v];       pushup(u);     }   }   void link(int u, int v) {     access(v);     splay(v);     access(u);     splay(u);     fa[u] = v;     ssiz[v] += siz[u];     sans[v] += ans[u];     sqsiz[v] += siz[u] * siz[u];     pushup(v);   }   void cut(int u, int v) {     access(u);     access(v);     splay(v);     splay(u);     fa[u] = 0;     ssiz[v] -= siz[u];     sans[v] -= ans[u];     sqsiz[v] -= siz[u] * siz[u];     pushup(v);   }   bool check(int u, int v) {     access(v);     splay(v);     splay(u);     if (isroot(v)) {       return false;     }     return true;   }   int main() {     scanf( %d , &n);     for (int i = 2; i <= n; i++) {       scanf( %d , &f[i]);     }     for (int i = 1; i <= n; i++) {       scanf( %lld , &a[i]);       ans[i] = all[i] = a[i];     }     for (int i = 1; i <= n; i++) {       siz[i] = 1;       ssiz[i] = 1;     }     for (int i = 2; i <= n; i++) {       link(i, f[i]);     }     access(1);     splay(1);     printf( %.10lf n , 1.0 * ans[1] / n / n);     scanf( %d , &m);     while (m--) {       scanf( %s%d%d , op, &x, &y);       if (op[0] ==  P ) {         if (check(x, y)) {           swap(x, y);         }         cut(x, f[x]);         f[x] = y;         link(x, f[x]);         access(1);         splay(1);         printf( %.10lf n , 1.0 * ans[1] / n / n);       } else {         access(x);         splay(x);         a[x] = y;         pushup(x);         printf( %.10lf n , 1.0 * ans[x] / n / n);       }     }     return 0;   }   