在 OI 界，有一位无人不知无人不晓，OI 水平前无古人后无来者的胡策，江湖人称一眼秒题胡大爷。

胡策最近从一名自称是小 O 的神秘男子那里收到了一棵神奇的小树苗。

这是一棵 $n$ 个节点的有根树，节点标号为 $1, \dots, n$，其中 $1$ 号点为根。

这棵有根树上每个点都有一个权值，点 $i$ 的权值为 $a_i$。$a_1, \dots, a_n$ 构成了一个 $0\sim n-1$ 的排列，且 $a_1=0$。

胡策大爷十分喜欢猴子，他打算在这棵树上养 $n$ 只猴子。初始时，每个节点上将放着恰好一只猴子。猴子们十分好动，每过一秒，每只在 $i$ 节点的猴子会设法往 $i$ 的父亲节点上跳，有 $p(i)$ 的概率成功跳到父亲节点；否则跳跃失败，将等概率地随机落到子树 $i$ 里某个节点上（包括点 $i$）。

因为根节点没有父亲，所以 $p(1)=0$。对于 $2\leq i\leq n$，有 $p(i)=\frac{a_i}{n}$；

在第 $i$ 秒，胡策会观察并记录这 $n$ 只猴子中成功跳上父亲结点的猴子所占的比例 $g_i$。胡策认为 $g_0, \dots, g_T$ 的平均值就是这群猴子们生活的幸福指数，为保证准确，其中 $T$ 为很大很大的值，为 $(n+1)^{99999^{99999^{99999}}}$

为了让猴子们的幸福指数的期望更大，胡策又从那名自称是小 O 的神秘男子那里买来了一袋叫“金坷垃”的肥料。如果给这棵有根树掺 $x$ 克的金坷垃，那么这棵树每个点 $i$ 的权值将变化成 $(a_i+x)\bmod n$。因为胡策是土豪有钱任性，$x$ 可以取任意非负整数。

请你告诉胡策，他该掺多少克的金坷垃，才能使猴子们幸福指数的期望最大呢？

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个用空格隔开的非负整数，第 $i$ 个为节点 $i$ 的父亲节点编号 $f_i$。（$f_1=0$，对于 $i>1$ 有 $1\leq f_i< i$）

第三行 $n$ 个用空格隔开的非负整数，为一个 $0\sim n-1$ 的排列，第 $i$ 个表示 $a_i$。

输出格式

一行一个实数，表示掺适量的金坷垃时的最大幸福指数期望。

你的答案被认为是正确的当且仅当你的答案与标准答案的绝对误差或相对误差不超过 $10^{-9}$。

3
0 1 1
0 1 2

0.266666667

样例二

见样例数据下载。

限制与约定

对于 10% 的数据：$n = 2$。

对于 20% 的数据：$n\leq 5$。

对于 30% 的数据：$n\leq 100$。

对于 50% 的数据：$n\leq 2000$。

对于 70% 的数据：$n\leq 100000$。

对于 100% 的数据：$2\leq n\leq 500000$。

数据保证有一定梯度。

数据都是随机生成的。即：节点 $i$ 的父亲是从 $1\sim i-1$ 中随机选取的，$a_1 \dots a_n$ 是一个 $0 \sim n-1$ 的随机排列。

时间限制：$2\texttt{s}$

空间限制：$256\texttt{MB}$

来源

中国国家集训队互测2015 - By 陈胤伯

下载

样例数据下载