Petya và Cây BST

Cho một cây nhị phân tìm kiếm (BST) gồm $n$ nút, trong đó mỗi nút hoặc là lá (0 con), hoặc là nút trong (đúng 2 con). Mỗi nút chứa một khóa nguyên dương phân biệt; với mỗi nút trong, mọi khóa trong cây con trái đều nhỏ hơn khóa của nút, và mọi khóa trong cây con phải đều lớn hơn khóa của nút.

Cho thêm $k$ khóa tìm kiếm, đều phân biệt và khác với mọi khóa trong cây. Với mỗi khóa tìm kiếm $q$, ta thực hiện tìm kiếm BST từ gốc: nếu khóa của nút hiện tại lớn hơn $q$ thì sang con trái, ngược lại sang con phải; lặp đến khi gặp lá. Vì $q$ không có trong cây, đường đi luôn kết thúc tại một lá nào đó và khóa của lá đó được lấy làm kết quả.

Tuy nhiên, trong quá trình tìm kiếm này ta mắc đúng một lỗi: tại đúng một nút trong nào đó trên đường đi, ta đi nhầm hướng (đi ngược lại so với so sánh đúng); ở các nút trong còn lại ta vẫn so sánh và rẽ đúng. Trên một đường tìm có $d$ nút trong (tính cả gốc), có đúng $d$ phương án "mắc đúng một lỗi" như vậy, và chúng được coi là đồng xác suất.

Với mỗi khóa tìm kiếm $q$, hãy tính kỳ vọng giá trị khóa tại lá mà thuật toán kết thúc, tính trung bình trên tất cả $d$ phương án mắc lỗi.

Dữ liệu vào

• Dòng đầu chứa một số nguyên lẻ $n$ ($3\le n<{10}^5$) — số nút của cây.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên cách nhau bởi dấu cách: chỉ số cha của nút $i$ và khóa của nút $i$. Với nút gốc, chỉ số cha được cho là $-1$. Các nút đánh số từ $1$ đến $n$.
• Dòng tiếp theo chứa một số nguyên $k$ ($1\le k\le {10}^5$) — số khóa tìm kiếm.
• $k$ dòng tiếp theo, mỗi dòng chứa một khóa tìm kiếm.

Tất cả $n+k$ khóa đều là số nguyên dương phân biệt, không vượt quá ${10}^9$. Dữ liệu vào đảm bảo cây mô tả là một BST hợp lệ; với mỗi nút khác gốc, từ khóa của nó có thể xác định nó là con trái hay con phải của cha.

Dữ liệu ra

In ra $k$ số thực, mỗi số trên một dòng, là kỳ vọng cần tìm cho từng khóa tìm kiếm theo thứ tự. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc tương đối không quá ${10}^{-9}$.

Ví dụ