CF85C.Petya and Tree

One night, having had a hard day at work, Petya saw a nightmare. There was a binary search tree in the dream. But it was not the actual tree that scared Petya. The horrifying thing was that Petya couldn't search for elements in this tree. Petya tried many times to choose key and look for it in the tree, and each time he arrived at a wrong place. Petya has been racking his brains for long, choosing keys many times, but the result was no better. But the moment before Petya would start to despair, he had an epiphany: every time he was looking for keys, the tree didn't have the key, and occured exactly one mistake. "That's not a problem!", thought Petya. "Why not count the expectation value of an element, which is found when I search for the key". The moment he was about to do just that, however, Petya suddenly woke up.

Thus, you are given a binary search tree, that is a tree containing some number written in the node. This number is called the node key. The number of children of every node of the tree is equal either to 0 or to 2. The nodes that have 0 children are called leaves and the nodes that have 2 children, are called inner. An inner node has the left child, that is the child whose key is less than the current node's key, and the right child, whose key is more than the current node's key. Also, a key of any node is strictly larger than all the keys of the left subtree of the node and strictly smaller than all the keys of the right subtree of the node.

Also you are given a set of search keys, all of which are distinct and differ from the node keys contained in the tree. For each key from the set its search in the tree is realised. The search is arranged like this: initially we are located in the tree root, if the key of the current node is larger that our search key, then we move to the left child of the node, otherwise we go to the right child of the node and the process is repeated. As it is guaranteed that the search key is not contained in the tree, the search will always finish in some leaf. The key lying in the leaf is declared the search result.

It is known for sure that during the search we make a mistake in comparing exactly once, that is we go the wrong way, but we won't make any mistakes later. All possible mistakes are equiprobable, that is we should consider all such searches where exactly one mistake occurs. Your task is to find the expectation (the average value) of the search result for every search key, considering that exactly one mistake occurs in the search. That is, for a set of paths containing exactly one mistake in the given key search, you should count the average value of keys containing in the leaves of those paths.

一天夜里，彼得亚在辛苦工作了一整天后做了一个噩梦。梦中出现了一棵二叉搜索树（BST）。真正令彼得亚恐惧的，并非这棵树本身，而是他无法在这棵树中成功查找元素。彼得亚多次尝试选定一个关键字并在树中搜索它，但每次到达的都是错误的位置。彼得亚苦思冥想许久，反复选择不同的关键字进行搜索，结果却毫无改善。就在彼得亚即将陷入绝望之际，他突然灵光一现：每次搜索时，目标关键字都不在树中，且恰好发生一次错误。“这根本不是问题！”彼得亚心想，“何不计算一下：当我搜索该关键字时，最终实际找到的那个元素的期望值呢？”正当他准备着手计算时，彼得亚却猛然惊醒。

因此，你将得到一棵二叉搜索树——即一棵每个节点中存储有一个数字的树；该数字称为节点关键字。树中每个节点的子节点数量要么为 0，要么为 2。拥有 0 个子节点的节点称为叶节点，拥有 2 个子节点的节点称为内节点。每个内节点具有一个左子节点（其关键字严格小于当前节点的关键字）和一个右子节点（其关键字严格大于当前节点的关键字）。此外，任意节点的关键字严格大于其左子树中所有节点的关键字，且严格小于其右子树中所有节点的关键字。

同时，你还被给定一个搜索关键字集合，其中所有关键字互不相同，且均不在树中出现。对集合中的每个关键字，均在树中执行一次搜索。搜索过程如下：初始时位于树根节点；若当前节点的关键字大于待搜索关键字，则移向其左子节点；否则（即当前节点关键字小于或等于待搜索关键字），则移向其右子节点；该过程不断重复。由于已知搜索关键字一定不在树中，搜索最终必定终止于某个叶节点。该叶节点中所存的关键字即被宣布为本次搜索的结果。

已知：在整个搜索过程中，恰好发生一次比较错误——即某一步我们走向了错误的方向（本该向左却向右，或本该向右却向左），但此后不再发生任何错误。所有可能的单次错误位置是等概率的，即我们需要考虑所有恰好含一次错误的搜索路径。你的任务是：对每个给定的搜索关键字，在所有恰好含一次错误的搜索路径中，求出这些路径最终抵达的叶节点中所含关键字的期望值（即平均值）。换言之，对给定关键字的所有含恰好一次错误的搜索路径，计算这些路径终点叶节点中关键字的平均值。

The first line contains an odd integer n (3 ≤ n < 105), which represents the number of tree nodes. Next n lines contain node descriptions. The (i + 1)-th line contains two space-separated integers. The first number is the number of parent of the i-st node and the second number is the key lying in the i-th node. The next line contains an integer k (1 ≤ k ≤ 105), which represents the number of keys for which you should count the average value of search results containing one mistake. Next k lines contain the actual keys, one key per line.

All node keys and all search keys are positive integers, not exceeding 109. All n + k keys are distinct.

All nodes are numbered from 1 to n. For the tree root "-1" (without the quote) will be given instead of the parent's node number. It is guaranteed that the correct binary search tree is given. For each node except for the root, it could be determined according to its key whether it is the left child or the right one.

第一行包含一个奇数 $n$（$3 \leq n < 10^5$），表示树中节点的数量。接下来的 $n$ 行描述各节点。第 $(i+1)$ 行包含两个以空格分隔的整数：第一个数是第 $i$ 个节点的父节点编号，第二个数是第 $i$ 个节点中存储的关键字。随后一行包含一个整数 $k$（$1 \leq k \leq 10^5$），表示需要计算平均搜索结果（含恰好一次错误）的关键字个数。接下来的 $k$ 行每行给出一个关键字。

所有节点关键字及所有搜索关键字均为不超过 $10^9$ 的正整数，且全部 $n + k$ 个关键字互不相同。

所有节点编号为 $1$ 至 $n$。对于树根节点，其父节点编号用 “-1”（不含引号）表示。保证输入构成一棵合法的二叉搜索树。对除根节点外的每个节点，均可根据其关键字唯一确定其为左子节点或右子节点。

Print k real numbers which are the expectations of answers for the keys specified in the input. The answer should differ from the correct one with the measure of absolute or relative error not exceeding 10 - 9.

输出 k 个实数，分别表示输入中指定的各密钥所对应答案的期望值。答案与正确值之间的绝对误差或相对误差不得超过 $10^{-9}$。

In the first sample the search of key 1 with one error results in two paths in the trees: (1, 2, 5) and (1, 3, 6), in parentheses are listed numbers of nodes from the root to a leaf. The keys in the leaves of those paths are equal to 6 and 10 correspondingly, that's why the answer is equal to 8.

在第一个样例中，对关键字 1 进行允许一个错误的搜索，在树中得到两条路径：(1, 2, 5) 和 (1, 3, 6)，括号内列出的是从根节点到叶节点的节点编号。这两条路径的叶节点中存储的关键字分别为 6 和 10，因此答案为 8。