题目描述

Amadea 和 Bilva 正在装饰一棵有根树，树包含 $N$ 个节点，编号为 $1$ 到 $N$。节点 $1$ 是树的根，所有其他节点的父节点编号都小于自身。

Amadea 和 Bilva 按以下方式装饰树：

• Amadea 均匀随机地选择一个树中的节点并涂色。然后，她沿着树向上走，每隔 $A$ 个节点涂色一次，直到到达根节点。
• Bilva 均匀随机地选择一个树中的节点并涂色。然后，她沿着树向上走，每隔 $B$ 个节点涂色一次，直到到达根节点。

树的美丽值等于至少被 Amadea 或 Bilva 涂色一次的节点数。注意，即使他们两人都涂了同一个节点，也只计算一次。

求树的美丽值的期望。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含三个整数 $N$、$A$ 和 $B$。第二行包含 $N-1$ 个整数，其中第 $i$ 个整数是节点 $i+1$ 的父节点。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是树的美丽值的期望。

如果 $y$ 与正确答案的绝对误差或相对误差在 $10^{-6}$ 以内，则认为正确。

3
8 2 3
1 1 3 4 4 3 4
10 3 4
1 1 1 1 1 1 1 1 1
4 3 1
1 2 3

Case #1: 2.65625
Case #2: 1.9
Case #3: 2.875

提示

限制条件

$1 \le T \le 100$。

$1 \le A \le N$。

$1 \le B \le N$。

测试集 1

$1 \le N \le 100$。

测试集 2

最多 $5$ 个测试用例满足 $1 \le N \le 5 \times 10^5$。

其余所有测试用例满足 $1 \le N \le 100$。

翻译由 DeepSeek V4 Pro 完成