func_code_string: #include <bits/stdc++.h>   using namespace std;   const int MAXN = 100005;   int n, m, far[MAXN], a[MAXN];   struct LCT {     int fa[MAXN], ch[MAXN][2];     int s[MAXN], xs[MAXN];     long long xs2[MAXN], sum[MAXN], ans[MAXN], xans[MAXN];     bool isroot(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }     int get(int x) { return ch[fa[x]][1] == x; }     void up(int x) {       s[x] = s[ch[x][0]] + s[ch[x][1]] + xs[x] + 1;       sum[x] = sum[ch[x][0]] + sum[ch[x][1]] + 1ll * a[x] * (xs[x] + 1);       ans[x] = ans[ch[x][0]] + ans[ch[x][1]] + xans[x] +                a[x] * (1ll * (xs[x] + 1) * (xs[x] + 1) - xs2[x]) +                2ll * a[x] * (xs[x] + 1) * s[ch[x][1]] +                2ll * sum[ch[x][0]] * (s[x] - s[ch[x][0]]);     }     void rotate(int x) {       int f1 = fa[x], f2 = fa[f1], id = get(x);       ch[f1][id] = ch[x][id ^ 1];       fa[ch[f1][id]] = f1;       if (!isroot(f1)) ch[f2][get(f1)] = x;       fa[x] = f2;       ch[x][id ^ 1] = f1;       fa[f1] = x;       up(f1);     }     void splay(int x) {       while (!isroot(x)) {         int f1 = fa[x];         if (!isroot(f1)) {           if (get(x) == get(f1))             rotate(f1);           else             rotate(x);         }         rotate(x);       }       up(x);     }     void access(int x) {       for (int y = 0; x; y = x, x = fa[x]) {         splay(x);         xs[x] += s[ch[x][1]] - s[y];         xs2[x] += 1ll * s[ch[x][1]] * s[ch[x][1]] - 1ll * s[y] * s[y];         xans[x] += ans[ch[x][1]] - ans[y];         ch[x][1] = y;         up(x);       }     }     void link(int x, int y) {       access(x), splay(x);       access(y), splay(y);       fa[x] = y;       xs[y] += s[x];       xans[y] += ans[x];       xs2[y] += 1ll * s[x] * s[x];       up(y);     }     void cut(int x, int y) {       access(y), splay(y);       splay(x);       fa[x] = 0;       xs[y] -= s[x];       xans[y] -= ans[x];       xs2[y] -= 1ll * s[x] * s[x];       up(y);     }     bool is_anc(int x, int y) {       access(y);       splay(y), splay(x);       return !isroot(y);     }     long long ask() {       splay(1);       return ans[1];     }     void modify(int x, int v) {       access(x), splay(x);       a[x] = v, up(x);     }   } tr;   char op[2];   int main() {     scanf( %d , &n);     for (int i = 2; i <= n; i++) scanf( %d , &far[i]);     for (int i = 1; i <= n; i++) scanf( %d , &a[i]);     for (int i = 1; i <= n; i++) tr.s[i] = 1;     for (int i = 2; i <= n; i++) tr.link(i, far[i]);     printf( %.10lf n , (double)tr.ask() / n / n);     scanf( %d , &m);     while (m--) {       int x, y;       scanf( %s%d%d , op, &x, &y);       if (op[0] ==  P ) {         if (tr.is_anc(x, y)) swap(x, y);         tr.cut(x, far[x]);         far[x] = y;         tr.link(x, far[x]);       } else         tr.modify(x, y);       printf( %.10lf n , (double)tr.ask() / n / n);     }     return 0;   }   