← 返回题目列表

Codeforces · 85/C

C. 彼佳和树

中文机器翻译题面 查看原题

一天晚上,在辛苦工作了一天之后,Petya 看到了一场噩梦。梦里有一棵二叉搜索树。但让彼佳害怕的并不是那棵真正的树。可怕的是,Petya无法在这棵树中搜索元素。 Petya多次尝试选择钥匙并在树上寻找它,但每次他都到达了错误的地方。 Petya绞尽脑汁,选择了很多次钥匙,但结果却不见好转。但就在彼佳开始绝望的那一刻,他突然顿悟:每次他寻找钥匙时,树上都没有钥匙,而且只出现了一个错误。 “这不是问题!”彼佳想。 “为什么不计算一个元素的期望值,当我搜索键时找到它”。然而,正当他要这么做的时候,彼佳突然醒了。

因此,您将获得一棵二叉搜索树,即一棵包含节点中写入的数字的树。这个数字称为节点密钥。树的每个节点的子节点数量等于 0 或 2。具有 0 个子节点的节点称为叶节点,具有 2 个子节点的节点称为内部节点。内部节点具有左子节点(即键小于当前节点键的子节点)和右子节点(其键大于当前节点的键)。此外,任何节点的键严格大于该节点左子树的所有键并且严格小于该节点右子树的所有键。

此外,您还会获得一组搜索键,所有这些搜索键都是不同的,并且与树中包含的节点键不同。对于集合中的每个键,其在树中的搜索都是实现的。搜索是这样安排的:最初我们位于树根中,如果当前节点的键大于我们的搜索键,那么我们移动到该节点的左子节点,否则我们移动到该节点的右子节点并重复该过程。由于可以保证搜索关键字不包含在树中,因此搜索将始终在某个叶子中完成。叶子中的键被声明为搜索结果。

可以肯定的是,在搜索过程中,我们在比较一次时犯了一个错误,那就是我们走错了路,但以后我们就不会再犯任何错误了。所有可能的错误都是等概率的,也就是说,我们应该考虑所有这样的搜索,其中恰好有一个错误发生。您的任务是在考虑到搜索中恰好出现一个错误的情况下,找到每个搜索键的搜索结果的期望(平均值)。也就是说,对于给定键搜索中恰好包含一个错误的一组路径,您应该计算这些路径的叶子中包含的键的平均值。

输入

第一行包含一个奇整数 n (3 ≤ n < 105),表示树节点的数量。接下来的 n 行包含节点描述。第 (i + 1) 行包含两个以空格分隔的整数。第一个数字是第 i 个节点的父节点编号,第二个数字是第 i 个节点中的密钥。下一行包含一个整数 k (1 ≤ k ≤ 105),它表示您应该计算包含一个错误的搜索结果的平均值的键的数量。接下来的 k 行包含实际的键,每行一个键。

所有节点键和所有搜索键都是正整数,不超过 109。所有 n + k 个键都是不同的。

所有节点的编号从 1 到 n。对于树根,将给出“-1”(不带引号)而不是父节点的节点号。保证给出正确的二叉搜索树。对于除根之外的每个节点,都可以根据其键来确定它是左子节点还是右子节点。

输出

打印 k 个实数,它们是输入中指定的键的答案期望。答案应与正确答案不同,且绝对或相对误差不超过 10 - 9。

示例

输入 #1

7
-1 8
1 4
1 12
2 2
2 6
3 10
3 14
1
1

输出 #1

8.0000000000

输入 #2

3
-1 5
1 3
1 7
6
1
2
4
6
8
9

输出 #2

7.0000000000
7.0000000000
7.0000000000
3.0000000000
3.0000000000
3.0000000000

注意

在第一个示例中,对键 1 的搜索有一个错误会导致树中出现两条路径:(1, 2, 5) 和 (1, 3, 6),括号中列出了从根到叶子的节点数。这些路径的叶子中的键分别等于 6 和 10,这就是为什么答案等于 8。