E. Модтой тоглоом

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Момижид $n$ ширхэг оройтой өлгөгдсөн мод (rooted tree) өгөгдсөн. Тэр модныхоо оройнуудыг $1$-ээс $n$ хүртэл дугаарлаад $1$ гэсэн оройноос нь модоо өлгөөд тоглоом тоглохоор шийдэв.

Тоглоом нь дараах байдлаар явагдана. Момижи модонд байгаа нэг оройг (энэ оройг $v$ гэж тэмдэглэе) сонгож аваад $v$ оройтой холбоогдсон бүх холбоосыг салгана. Тэгвэл $v$ оройноос унжиж байсан оройнууд ч бас модноос салах юм. Мод нь ямар ч оройгүй үлдсэн тохиолдолд тоглоом дуусна. Өөрөөр хэлбэл $1$ гэсэн оройг салгахад тоглоом дуусах юм.

Момижи үргэлж модонд үлдсэн байгаа оройнуудаас сонгож авч салгадаг. Таны даалгавар бол тоглоом дунджаар хэдэн үйлдлийн дараа өндөрлөхийг тооцоолох юм.

Оролт

Эхний мөрөнд мод хэдэн оройтойг тодорхойлох $n$ ($1 ≤ n ≤ 10^5$) тоо өгөгдөнө. Дараагийн $n - 1$ мөрөнд модны холбоосуудыг өгнө. $i$ дахь холбоосоор ямар хоёр орой холбогдсоныг илтгэх $a_i, b_i$ ($1 ≤ a_i, b_i ≤ n; a_i ≠ b_i$) тоонууд өгөгдөнө.

Өгсөн граф заавал мод байна.

Гаралт

Дунджаар хэдэн үйлдлийн дараа тоглоом дуусахыг илтгэх ганц эерэг бодит тоо.

Хариунд гарсан тоо нь $10^{-6}$ зэрэгт зөрөөгүй тохиолдолд зөв хариунд авч үзнэ.

Орчуулсан: Энхсанаа

Жишээ тэстүүд

Оролт
2
1 2
Гаралт
1.50000000000000000000
Оролт
3
1 2
1 3
Гаралт
2.00000000000000000000

Тэмдэглэл

In the first sample, there are two cases. One is directly remove the root and another is remove the root after one step. Thus the expected steps are:

$1 × (1 / 2) + 2 × (1 / 2) = 1.5$

In the second sample, things get more complex. There are two cases that reduce to the first sample, and one case cleaned at once. Thus the expected steps are:

$1 × (1 / 3) + (1 + 1.5) × (2 / 3) = (1 / 3) + (5 / 3) = 2$

Сэтгэгдлүүдийг ачааллаж байна...