在 OI 界，有一位无人不知无人不晓，OI 水平前无古人后无来者的胡策，江湖人称一眼秒题胡大爷。
胡策最近从一名自称是小 O 的神秘男子那里收到了一棵神奇的小树苗。
这是一棵 $n$ 个节点的有根树，节点标号为 $1, \cdots, n$，其中 $1$ 号点为根。
这棵有根树上每个点都有一个权值，点 $i$ 的权值为 $a_i$。$a_1, \cdots, a_n$ 构成了一个 $0 \sim n-1$ 的排列，且 $a_1 = 0$。
胡策大爷十分喜欢猴子，他打算在这棵树上养 $n$ 只猴子。初始时，每个节点上将放着恰好一只猴子。猴子们十分好动，每过一秒，每只在 $i$ 节点的猴子会设法往 $i$ 的父亲节点上跳，有 $p \left( i \right)$ 的概率成功跳到父亲节点；否则跳跃失败，将等概率地随机落到子树 $i$ 里某个节点上 (包括点 $i$)。
因为根节点没有父亲，所以 $p \left( 1 \right) = 0$。对于 $2 \leq i \leq n$，有 $p \left( i \right) = \dfrac {a_i} n$；
在第 $i$ 秒，胡策会观察并记录这 $n$ 只猴子中成功跳上父亲结点的猴子所占的比例 $g_i$。胡策认为 $g_0, \dots, g_T$ 的平均值就是这群猴子们生活的幸福指数，为保证准确，其中 $T$ 为很大很大的值，为 $\left (n + 1 \right)^{99999^{99999^{99999}}}$。
为了让猴子们的幸福指数的期望更大，胡策又从那名自称是小 O 的神秘男子那里买来了一袋叫 "金坷垃" 的肥料。如果给这棵有根树掺 $x$ 克的金坷垃，那么这棵树每个点 $i$ 的权值将变化成 $\left( a_i + x \right) \bmod n$。因为胡策是土豪有钱任性，$x$ 可以取任意非负整数。
请你告诉胡策，他该掺多少克的金坷垃，才能使猴子们幸福指数的期望最大呢？
第一行包含一个正整数 $n$ ($n \leq 5 \times 10^5$)。
第二行包含 $n$ 个用空格隔开的非负整数 $f_1, f_2, \cdots, f_n$ ($f_1 = 0; \forall 1 < i \leq n, 1 \leq f_i < i$)，第 $i$ 个为节点 $i$ 的父亲节点编号 $f_i$。
第三行包含 $n$ 个用空格隔开的非负整数 $a_1, a_2, \cdots, a_n$ ($a_1 = 0$，且 $a_1, a_2, \cdots, a_n$ 构成了一个 $0 \sim n - 1$ 的排列)，表示每个点的权值。
保证数据都是随机生成的。即：$f_i$ 是从 $1 \sim i - 1$ 中的所有整数等概率随机选取的，$a_2, \cdots, a_n$ 是从 $1 \sim n - 1$ 的所有排列中等概率随机选取的。
输出一行一个实数，表示掺适量的金坷垃时的最大幸福指数期望。答案被认为正确当且仅当相对或绝对误差不超过 $10^{-9}$。
由期望的线性性质，我们只需考虑每个猴子对最后幸福指数的期望的贡献，最后再求和即可。
先考虑不掺金坷垃的情况，对于一只固定的猴子，由于 $T \to + \infty$，因此它对期望的贡献就是它在无穷多次的跳跃活动中形如 "$v \to p_v$" 的跳跃的出现频率，换句话说，就是每次跳跃为成功跳跃的概率。
因为 $T \to + \infty$，且 $a_1 = 0, a_i > 0$ ($i > 1$)，因此一只猴子一定可以以 $1$ 的概率在有限步内跳到根，因此每只猴子对最后期望的贡献与猴子的初始位置无关，都是相同的。
考虑在这 $+ \infty$ 次过程中，一只猴子在点 $i$ 的频率 (概率) 为 $x_i$，则这只猴子对整个期望的贡献为 $\dfrac 1n \sum\limits_v x_v p \left( v \right)$。$n$ 只猴子的贡献组合 (即答案) 就等于 $\sum\limits_v x_v p \left( v \right)$。
现在的任务就转化为了求所有的 $x_i$。
注意到猴子的跳跃过程可以看作是在树上的一个 "随机游走" 过程，因此可以考虑列出方程组。
考察一个点 $v$，有哪些可以到达 $v$。
首先是跳跃成功的方案：对于 $v$ 的直接子节点 $c$，有 $p_c$ (注：$p_c = p \left( c \right)$，下文为了方便记为 $p_c$) 的概率跳回 $v$，故 $x_v \gets p_c \cdot x_c$。
对于 $v$ 的一个祖先节点 (含 $v$ 自身) $a$，有 $1 - p_a$ 的概率跳跃失败，在跳跃失败的条件下又有 $\dfrac 1 {size_a}$ 的条件概率回到 $c$，因此贡献为 $x_v \gets \dfrac {1 - p_a} {size_a} \cdot x_a$。
综上，$$ x_v = \sum_{p_c = v} p_c \cdot x_c + \sum_{a \in anc(v)} \frac {1 - p_a} {size_a} \cdot x_a \tag 1 \label 1 $$
对于每个节点 $v$，我们都可以列出一个形如 $\eqref 1$ 式的方程，于是我们就得到了一个 $n$ 元的线性方程组。
尝试使用 Gauss 消元去解决它。不过眼尖的同学马上就发现了：这是一个齐次线性方程组！因此有无穷多组解。我们需要加入一个限制条件：$x_1 + x_2 + \cdots + x_n = 1$，这样解就唯一了。
不过裸的 Gauss 消元需要 $O \left( n^3 \right)$ 的时间复杂度，无法接受。注意到它是在树上的消元问题，我们仿照 [PKUWC2018]随机游走，尝试在 $O \left( n \right)$ 的时间内完成消元。
类似地思想，我们对每个节点 $v$，尝试去算出一个系数 $\kappa_v$，使得 $x_v = \kappa_v \cdot x_{p_v}$。不过这里由于有 "$\displaystyle \sum_{a \in anc(v)} \frac {1 - p_a} {size_a} \cdot x_a$" 这一项的存在，因此直接表示似乎遇到了困难。
注意这一项的形式，可以看出，这大概就是一个 "前缀和"！因此我们考虑使用差分来进行换元，即令 $\displaystyle X_v = \sum_{a \in anc(v)} \frac {1 - p_a} {size_a} \cdot x_a$，则 $x_v = \dfrac {size_a} {1 - p_a} \left( X_v - X_{p_v} \right)$。
将其代入 $\eqref 1$ 式，得到：
$$ \frac {size_a} {1 - p_a} \left( X_v - X_{p_v} \right) = X_v + \sum_{c, p_c = v} \frac {p_c \cdot size_c} {1 - p_c} \left( X_c - X_v \right) \tag 2 \label 2 $$
于是我们就得到了一个只关于 $X_c, X_v, X_{p_v}$ 的方程，就可以像那道题一样进行递推 (树上消元) 了，时间复杂度是 $O \left( n \right)$ 的。
考虑最后要计算的表达式 $\sum\limits_v x_v \cdot p_v$，可以在消元的过程记录一下当前 $\dfrac {\sum_i x_i \cdot p_i} {x_1}$ 和 $\dfrac {\sum_i x_i} {x_1}$ 的相对值，最后 "比一比" 即可得到答案 (由于 $\sum\limits_i x_i = 1$)。
于是我们可以在 $O \left( n \right)$ 时间内解决不掺金坷垃时的问题。
那么如果掺了金坷垃，问题又该怎么处理呢？
$O \left( n^2 \right)$ 暴力？动态消元？动态 DP？数据结构优化？
别想复杂了！注意到题目中的一大关键条件：数据随机！这启发我们尝试使用暴力，并证明它的复杂度。
考虑掺和了金坷垃的情况，显然答案只和 $x \bmod n$ 的值有关，故不妨假设 $1 \leq x < n$。注意到另一个条件：$a_2, a_3, \cdots, a_n$ 恰好构成一个 $1 \sim n - 1$ 的排列！
因此，对于 $\forall 1 \leq x < n$，恰好存在唯一对应的 $2 \leq i \leq n$，满足 $a_i = n - x$！
于是，如果掺和了 $x \,\mathrm g$ 的金坷垃，则对应的 $i = i \left( x \right)$ 号点的 $a'_i$ 将会变成 $0$！那么 $p'_i$ 也会等于 $0$，换句话说，就是 $i$ 这个点永远无法跳跃成功！
从而，对任意一只猴子，它将以 $1$ 的概率在有限步内跳到以 $i$ 为根的子树中。因此在考虑最终无穷次的期望时，只需考虑这棵 $i$ 子树就可以了！
于是，我们把问题转为了一个规模为 $size_i$ 的子问题，在子问题中使用前面暴力的 Gauss 树上消元即可，复杂度 $O \left( size_i \right)$。
接下来就是引人注目的复杂度分析环节啦！
$$ T \left( n \right) \leq O \left( size_1 \right) + O \left( size_2 \right) + \cdots + O \left( size_n \right) \leq O \left( size_1 + size_2 + \cdots + size_n \right) = O \left( dep_1 + dep_2 + \cdots + dep_n \right) = O \left( H_1 + H_2 + \cdots + H_n \right) = O \left( n \log n \right) $$
也就是说，在树的形态随机的情况下，上述算法的时间复杂度是 $O \left( n \log n \right)$ 的。故我们证明了该算法的时间复杂度正确性。
#include <bits/stdc++.h>
const int N = 500054;
int n;
int p[N], fc[N], nc[N];
int cnt = 0, o[N], id[N], eid[N];
int a[N], size[N];
double ratio[N], sum[N], sumw[N];
double ans = 0.0, in, isize[N];
inline void up(double &x, const double y) {x < y ? x = y : 0;}
inline void link(int x, int px) {nc[x] = fc[px], fc[px] = x;}
double solve(int x) {
double pr, K, L;
int *v, *re = o + (id[x] - 1), weight;
for (v = o + eid[x]; v != re; --v) ratio[*v] = 1., sum[*v] = sumw[*v] = 0.;
for (v = o + eid[x]; v != re; --v) {
weight = (a[*v] - a[x] + n) % n, pr = weight * in, K = (1. - pr) * isize[*v], L = size[*v] / (1. - pr);
ratio[*v] = 1. / (1. - K * ratio[*v]), ratio[p[*v]] += (ratio[*v] - 1.) * pr * L;
if (*v == x) sum[x] += size[x], sumw[x] += pr * size[x];
else sum[p[*v]] += sum[*v] += (sum[*v] + L) * (ratio[*v] - 1.), sumw[p[*v]] += sumw[*v] += (sumw[*v] + pr * L) * (ratio[*v] - 1.);
}
return sumw[x] / sum[x];
}
void dfs(int x) {
int y; o[++cnt] = x, id[x] = cnt;
for (y = fc[x]; y; y = nc[y]) dfs(y);
eid[x] = cnt, size[x] = eid[x] - id[x] + 1, isize[x] = 1. / (double)size[x];
}
int main() {
int i;
scanf("%d", &n), in = 1. / (double)n;
for (i = 1; i <= n; ++i) scanf("%d", p + i), link(i, p[i]);
for (i = 1; i <= n; ++i) scanf("%d", a + i);
dfs(1);
for (i = 1; i <= n; ++i) up(ans, solve(i));
return printf("%.12lg\n", ans), 0;
}
坑1：在解方程时不要把式子推错，比如移项时要记得变号。
坑2：注意浮点运算精度和速度问题，比如可以预处理倒数什么的。