func_code_string: #include <bits/stdc++.h>   using namespace std;   const int maxn = 50000 + 10;   struct query {     int type, x, y;   } qu[maxn];   int n, fa[maxn];   long long val[maxn], sz[maxn];   vector<int> v[maxn];   bool mark[maxn], have[maxn];   long long d[maxn];   int dfs(int x) {     sz[x] = 1;     int ret = 0;     for (auto i : v[x]) ret += dfs(i), sz[x] += sz[i];     for (auto i : v[x]) d[i] = (sz[x] - sz[i]) * val[x];     have[x] = ((ret || mark[x]) ? 1 : 0);     if (ret >= 2 || mark[x]) {       mark[x] = 1;       return 1;     } else       return ret;   }   struct P {     int to, ssum;     long long dsum;   };   vector<P> v2[maxn];   int fa2[maxn];   long long sz2[maxn], sz2sum[maxn];   long long pnum[maxn];   bool leaf[maxn];   void dfs2(int x, bool isfir = 0) {     if (v2[x].empty()) {       if (!isfir) return;       pnum[x] = sz[x] * sz[x];       for (auto i : v[x]) pnum[x] -= sz[i] * sz[i];       return;     }     sz[x] = 1 + sz2[x];     pnum[x] = 0;     for (auto i : v2[x])       dfs2(i.to, isfir), sz[x] += sz[i.to] + i.ssum,           pnum[x] -= (sz[i.to] + i.ssum) * (sz[i.to] + i.ssum);     pnum[x] += sz[x] * sz[x] - sz2sum[x];   }   int getid(int x, int y) {     for (int i = 0;; i++)       if (v2[x][i].to == y) return i;   }   void build_graph(int num) {     fill(mark, mark + n + 1, 0);     fill(have, have + n + 1, 0);     fill(leaf, leaf + n + 1, 1);     for (int i = 1; i <= n; i++) v[i].clear(), v2[i].clear();     for (int i = 2; i <= n; i++) v[fa[i]].push_back(i);     for (int i = 0; i < num; i++) {       mark[qu[i].x] = 1;       if (qu[i].type == 1) mark[qu[i].y] = 1;     }     mark[1] = 1;     dfs(1);     for (int i = 1; i <= n; i++)       if (mark[i]) {         sz2[i] = sz2sum[i] = 0;         for (auto j : v[i])           if (!have[j]) sz2[i] += sz[j], sz2sum[i] += sz[j] * sz[j];         if (i == 1) continue;         int j, ssum = 0;         long long dsum = 0LL;         for (j = i;; j = fa[j]) {           dsum += d[j];           if (mark[fa[j]]) break;         }         ssum = sz[j] - sz[i];         j = fa[j];         v2[j].push_back((P){i, ssum, dsum});         fa2[i] = j;         leaf[j] = 0;       }   }   bool first = 1;   void process(int num) {     build_graph(num);     long long nowans = 0LL, tot = (long long)n * n;     for (int i = 1; i <= n; i++) {       long long add = sz[i] * sz[i];       for (auto j : v[i]) add -= sz[j] * sz[j];       nowans += add * val[i];     }     if (first) printf( %.15f n , ((double)nowans) / tot), first = 0;     dfs2(1, 1);     for (int i = 0; i < num; i++) {       if (qu[i].type == 2) {         int x = qu[i].x, nval = qu[i].y;         nowans += pnum[x] * (nval - val[x]);         for (auto &j : v2[x])           j.dsum += (sz[x] - j.ssum - sz[j.to]) * (nval - val[x]);         val[x] = nval;         printf( %.15f n , ((double)nowans) / tot);         continue;       }       int x = qu[i].y, y = qu[i].x, id;       for (int j = x; j != 1; j = fa2[j])         if (j == y || y == 1) {           swap(x, y);           break;         }       fa[y] = x;       long long dif = 0LL;       for (int j = y; j != 1; j = fa2[j]) {         sz[fa2[j]] -= sz[y];         for (auto &k : v2[fa2[j]])           if (k.to != j)             k.dsum -= val[fa2[j]] * sz[y];           else             dif -= k.dsum;       }       int f = fa2[y];       id = getid(f, y);       sz2[f] += v2[f][id].ssum;       sz2sum[f] += (long long)v2[f][id].ssum * v2[f][id].ssum;       swap(v2[f][id], v2[f][v2[f].size() - 1]);       v2[f].pop_back();       v2[x].push_back((P){y, 0, val[x] * sz[x]});       fa2[y] = x;       if (v2[f].empty()) pnum[f] = sz[f] * sz[f] - sz2sum[f];       for (int j = y; j != 1; j = fa2[j]) {         sz[fa2[j]] += sz[y];         for (auto &k : v2[fa2[j]])           if (k.to != j)             k.dsum += val[fa2[j]] * sz[y];           else             dif += k.dsum;       }       nowans += 2 * dif * sz[y];       printf( %.15f n , ((double)nowans) / tot);       dfs2(1);     }   }   int main() {     scanf( %d , &n);     fa[1] = 1;     for (int i = 2; i <= n; i++) scanf( %d , &fa[i]);     for (int i = 1; i <= n; i++) scanf( %I64d , &val[i]);     int Q;     scanf( %d , &Q);     int sq = (int)sqrt(Q + 0.5);     for (int i = 0; i < Q; i++) {       char c[5];       scanf( %s%d%d , c, &qu[i % sq].x, &qu[i % sq].y);       qu[i % sq].type = (c[0] ==  P  ? 1 : 2);       if ((i % sq) == sq - 1 || i == Q - 1) process(i % sq + 1);     }   }   