B. Оньснууд

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

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

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

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

Барни USC (Чарзийн нэгдсэн улс) улсад амьдардаг. USC-д $1$-c $n$ хүртэл дугаарлагдсан $n$ хот болон тэдгээрийг холбосон $n - 1$ зам байна. USC-н хотууд болон замууд нь үндэстэй мод бүрдүүлнэ (энэ мод нь яагаад үндэстэй байгааг Барни сайн мэдэхгүй). Модны үндэс нь $1$ дугаартай хот. Иймээс хэрвээ аялалаа $1$ дугаартай хотоос эхлүүлбэл дээрх замуудаар хүссэн хотдоо очиж болно.

Нэг охин Барнигийн зүрхийг хулгайлсан ба Барни түүнийг олохыг хүсч байна. Тэр модны үндсээс эхлэн хайх ба (тэр Барни Стинсон болохоос санамсаргүй залуу биш учраас) хотуудаар хайхдаа $DFS$ алгоритм ашиглана. Энэ алгоритмын псеудо код нь:

let starting_time be an array of length n  
current_time = 0  
dfs(v):  
    current_time = current_time + 1  
    starting_time[v] = current_time  
    shuffle children[v] randomly (each permutation with equal possibility)  
    // children[v] is vector of children cities of city v  
    for u in children[v]:  
        dfs(u)

Өмнө хэлсэнчлэн Барни аялалаа модны үндсээс ($dfs(1)$ гэж дуудсантай ижил) эхэлнэ.

Одоо Барни үүргэвчээ баглах хэрэгтэй ба аялалынхаа талаар илүү ихийг мэдэхийг хүсч байна: $i$ хот бүрийн хувьд Барни $starting\_time[i]$-н тооцоолсон утгыг мэдэхийг хүсч байна. Тэр Жон Снөвийн найз ба юу ч мэдэхгүй учраас таны тусламжийг хүсч байна.

Оролт

Оролтын эхний мөрөнд бүхэл тоон утга $n$ ($1 ≤ n ≤ 10^{5}$) байх буюу USC-н хотуудын тоо.

Хоёр дахь мөрөнд $n - 1$ бүхэл тоон утга $p_{2}, p_{3}, ..., p_{n}$ ($1 ≤ p_{i} < i$) байх ба энд $p_{i}$ нь модон дахь $i$ дугаартай хотын эцэг хотын дугаар байх ба энэ нь USC-д $p_{i}$ ба $i$ хотуудыг холбосон зам байна гэсэн үг.

Гаралт

Гаралтын нэг мөрөнд $n$ тоо гаргах ба энд $i$-р тоо нь $starting\_time[i]$-н тооцоолсон утга юм.

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

Орчуулсан: Г.Мэндбаяр

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

Оролт
7
1 2 1 1 4 4
Гаралт
1.0 4.0 5.0 3.5 4.5 5.0 5.0 
Оролт
12
1 1 2 2 4 4 3 3 1 10 8
Гаралт
1.0 5.0 5.5 6.5 7.5 8.0 8.0 7.0 7.5 6.5 7.5 8.0 
Сэтгэгдлүүдийг ачааллаж байна...