Câu đố duyệt cây

Cho một cây có gốc gồm $n$ đỉnh, đánh số từ $1$ đến $n$. Gốc của cây là đỉnh $1$.

Ta duyệt cây bằng thuật toán DFS ngẫu nhiên sau, bắt đầu từ gốc (gọi dfs(1)):

current_time = 0
dfs(v):
    current_time = current_time + 1
    starting_time[v] = current_time
    xáo trộn ngẫu nhiên danh sách con của v (mỗi hoán vị có xác suất bằng nhau)
    for u in các con của v:
        dfs(u)

Tại mỗi đỉnh, thứ tự duyệt các con được chọn ngẫu nhiên đều trong tất cả các hoán vị. Với mỗi đỉnh $i$, hãy tính kỳ vọng của $starting\_time[i]$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số đỉnh của cây.
• Dòng thứ hai chứa $n-1$ số nguyên $p_2,p_3,\dots ,p_n$, trong đó $p_i$ là cha của đỉnh $i$. Khi $n=1$ dòng này rỗng.

Dữ liệu ra

In ra $n$ số thực, số thứ $i$ là kỳ vọng của $starting\_time[i]$.

Đáp án được chấp nhận nếu sai số tuyệt đối hoặc tương đối không vượt quá ${10}^{-6}$.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le p_i<i$

Ví dụ