CF85C Petya and Tree

给定一棵二叉搜索树，包含 $n$ 个节点，保证每个节点只可能有 $0$ 或 $2$ 个子节点。 再给定 $k$ 次询问，每次询问给出一个值 $x_i$ ， 对于第 $i$ 次询问，将 $x_i$ 插入树中，在插入过程中会等概率的“走错”（即在到达某个点时如果该往左子树走，则该往右子树走，反之亦然）恰好一次，输出该节点插入后的父节点的权值的期望值。（询问之间相互独立，即不会真正插进去） tips： 二叉搜索树的定义：如果一棵二叉树满足其任意一节点中，左子树的所有点的权值均小于该点权值且右子树的所有点的权值均大于该点权值（忽略空子树），则这棵树被称为二叉搜索树。 二叉搜索树的插入操作：最初位于树根，如果当前节点的权值大于要插入的节点的权值，那么移动到该节点的右子节点，否则移动到该节点的左子节点并重复该过程直到该节点为空。

共 $n + k + 2$ 行，第一行一个奇数 $n$ ，表示树中节点的个数（$ 3 \leqslant n \leqslant 10^{5} $）。 后面 $n$ 行中第 $i + 1$ 行包含两个以空格分隔的整数，第一个数字是节点 $i$ 父节点的编号 $f_i$ $ ( 1 \leqslant f_i \leqslant n $，$f_i = -1$ 表示 $i$ 是根节点） ，第二个数字是节点 $i$ 的权值 $a_i$ $ ( 1 \leqslant a_i \leqslant 10^{9} )$ 。 下一行包含一个整数 $k$ $ ( 1 \leqslant k \leqslant 10^{5} )$，表示询问次数。后面 $k$ 行中第 $n + i + 1$ 行每行一个整数 $x_i$ $ ( 1 \leqslant x_i \leqslant 10^{9} )$，表示第 $i$ 次询问要插入的值。 保证所有 $x_i, a_i$ 均不相同，保证给出的二叉搜索树正确。

共 $n$ 行，第 $i$ 行有一个实数，表示第 $i$ 次询问的答案，如果该数与答案误差在 $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.