Cây Con Biến Mất · canuc80k5525

Cho một cây gồm $n$ đỉnh, được đặt gốc tại đỉnh $1$ . Quan hệ tổ tiên và cây con luôn được hiểu theo gốc này.

Ban đầu, mọi đỉnh đều còn tồn tại. Mỗi lượt thực hiện như sau:

Chọn ngẫu nhiên đều một đỉnh trong số các đỉnh đang còn tồn tại.
Xóa đỉnh vừa chọn cùng tất cả các hậu duệ của nó vẫn còn tồn tại.

Quá trình kết thúc khi không còn đỉnh nào. Hãy tính kỳ vọng số lượt đã thực hiện.

Input

Dòng đầu chứa số nguyên $n$ - số đỉnh của cây.
$n - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ , biểu diễn một cạnh nối hai đỉnh đó.

Output

In một số thực - kỳ vọng số lượt cho đến khi cây rỗng.
Kết quả được chấp nhận nếu sai số tuyệt đối hoặc tương đối không vượt quá $1 0^{- 6}$ .

Constraints

$1 \leq n \leq 1 0^{5}$ .
$1 \leq u, v \leq n$ .
Các cạnh tạo thành một cây.

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 8$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

2.666666666667

Giải thích: Xác suất một đỉnh được chọn trực tiếp bằng nghịch đảo số đỉnh trên đường từ gốc đến nó. Năm đóng góp lần lượt là $1, 1/2, 1/2, 1/3, 1/3$ , nên tổng kỳ vọng bằng $8/3$ .

Hướng giải: Đặt I_v = 1 nếu đỉnh v được chọn trực tiếp trong một lượt; nếu v biến mất do một tổ tiên của nó được chọn trước thì đặt I_v = 0.
Hướng giải: Mỗi lượt tương ứng với đúng một đỉnh được chọn trực tiếp, vì vậy số lượt là
Hướng giải:

text X = sum I_v. - Hướng giải: Theo tính tuyến tính của kỳ vọng, - Hướng giải:

text E[X] = sum P(I_v = 1). - Hướng giải: Gán trước cho mỗi đỉnh một mức ưu tiên ngẫu nhiên khác nhau. Ở mỗi thời điểm, chọn đỉnh còn tồn tại có ưu tiên nhỏ nhất. Cách sinh quá trình này tương đương với việc chọn đều một đỉnh đang còn lại. - Hướng giải: Xét đỉnh v. Chỉ các đỉnh trên đường từ gốc đến v mới có thể xóa v trước khi nó được chọn. Đỉnh v được chọn trực tiếp khi và chỉ khi ưu tiên của nó nhỏ nhất trên đường đó. Nếu đường có depth[v] đỉnh thì các đỉnh đối xứng nhau, nên - Hướng giải:

text P(I_v = 1) = 1 / depth[v]. - Hướng giải: Do đó đáp án là - Hướng giải:

text sum_v 1 / depth[v], - Hướng giải: trong đó depth[1] = 1. Ta chỉ cần duyệt cây một lần để tính độ sâu. - Chứng minh đúng: Nếu một tổ tiên của v được chọn trước v, thao tác đó xóa toàn bộ cây con chứa v, nên v không thể được chọn trực tiếp. Ngược lại, nếu v có ưu tiên nhỏ nhất trên đường từ gốc đến nó, không tổ tiên nào được chọn trước v; các đỉnh ngoài đường này không thể xóa v, nên v chắc chắn còn tồn tại đến lượt của mình. - Chứng minh đúng: Vì thế biến chỉ báo I_v bằng 1 đúng khi v đứng sớm nhất trong tập các đỉnh trên đường gốc-v. Xác suất đó là 1/depth[v]. Cộng mọi xác suất bằng tuyến tính kỳ vọng cho đúng kỳ vọng số lượt. - Độ phức tạp: Thời gian O(n) và bộ nhớ O(n).