คำอธิบายโจทย์

บริษัทแห่งหนึ่งประกอบด้วยสมาชิก $n$ คนที่มีรหัสพนักงาน $1, 2, \dots, n$ สมาชิกหมายเลข $1$ คือเจ้านาย และสมาชิกคนอื่นๆ ทุกๆ คน $i$ ($2 \le i \le n$) จะมีหัวหน้างานโดยตรงคือ $f_i$ ($1 \le f_i < i$) โครงสร้างของบริษัทมีลักษณะเป็นต้นไม้มีรากโดยมีสมาชิกหมายเลข $1$ เป็นราก

ในบริษัทนี้ สมาชิก $a$ รู้จักสมาชิก $b$ ก็ต่อเมื่อเป็นไปตามเงื่อนไขอย่างน้อยหนึ่งข้อต่อไปนี้:

• $a = b$
• $b$ เป็นบรรพบุรุษของ $a$ กล่าวอีกนัยหนึ่งคือ มีลำดับ $u_1, u_2, \dots, u_k$ ($2 \le k$) ที่ทำให้ $u_1 = a$, $u_k = b$ และ $u_i = f_{u_{i-1}}$ สำหรับทุกๆ $2 \le i \le k$
• $b$ เป็นลูกโดยตรงของ $a$ ($b$ เป็นลูกน้องโดยตรงของ $a$) กล่าวอีกนัยหนึ่งคือ $f_b = a$

โปรดสังเกตว่าความสัมพันธ์ของการรู้จักกันไม่จำเป็นต้องสมมาตร นั่นคือ การที่ $a$ รู้จัก $b$ ไม่ได้หมายความว่า $b$ จะรู้จัก $a$

ตอนนี้ สมาชิกกำลังเล่นเกมกัน ในแต่ละรอบ สมาชิกที่กำหนด $m$ จะทำหน้าที่เป็นผู้ทาย และสมาชิกอีกคนหนึ่ง $p$ คือเป้าหมาย รับประกันว่า $p$ เป็นสมาชิกที่ $m$ ไม่รู้จัก

เพื่อระบุตัวตนของ $p$ สมาชิก $m$ จะถามคำถามเป็นลำดับ สำหรับแต่ละคำถาม $m$ จะเลือกรหัสพนักงาน $x$ แล้วถามว่า: "$p$ รู้จักสมาชิก $x$ หรือไม่?" สมาชิก $p$ จะตอบตามความจริงเสมอ นอกจากนี้ หาก $x = p$ สมาชิก $p$ จะเปิดเผยโดยเฉพาะว่าตนเองคือสมาชิก $x$ ซึ่งจะทำให้เกมจบลงทันที

แต่ละคำถามจะมีค่าใช้จ่ายในการเดินทางตามต้นไม้ของบริษัท หากคำถามที่ $i$ เกี่ยวข้องกับสมาชิก $x_i$ ค่าใช้จ่ายของคำถามนั้นคือ $dis(x_{i-1}, x_i)$ โดยที่ $dis(a, b)$ คือจำนวนเส้นเชื่อมบนเส้นทางเดียวระหว่าง $a$ และ $b$ ในต้นไม้ สำหรับคำถามแรก ($i = 1$) ค่าใช้จ่ายคือ $dis(m, x_1)$

สมาชิก $m$ ฉลาดมากและใช้กลยุทธ์ที่เหมาะสมที่สุดเพื่อลดค่าใช้จ่ายรวมที่จำเป็นในการรับประกันว่าเกมจะจบลงในกรณีที่เลวร้ายที่สุด (worst-case scenario) ให้เหลือน้อยที่สุด งานของคุณคือคำนวณค่าใช้จ่ายในกรณีที่เลวร้ายที่สุดที่น้อยที่สุดนี้สำหรับผู้ทายที่เป็นไปได้ทุกคน $m \in \{1, 2, \dots, n\}$

หากสมาชิก $m$ รู้จักทุกคนในบริษัทอยู่แล้ว คำตอบสำหรับ $m$ นั้นคือ $0$

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $n$ ($1 \le n \le 10^5$) แทนจำนวนสมาชิกทั้งหมดในบริษัท

บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n - 1$ จำนวน แทน $f_2, f_3, \dots, f_n$ โดยสอดคล้องกับ $1 \le f_i < i$

ข้อมูลส่งออก

พิมพ์บรรทัดเดียวที่ประกอบด้วยจำนวนเต็ม $n$ จำนวน แทนคำตอบสำหรับกรณีที่ $m = 1, m = 2, \dots, m = n$ โดยคั่นแต่ละจำนวนด้วยช่องว่าง

ตัวอย่าง

ข้อมูลนำเข้าตัวอย่าง 1

3
1 1

ข้อมูลส่งออกตัวอย่าง 1

0 2 2

ข้อมูลนำเข้าตัวอย่าง 2

5
1 1 3 2

ข้อมูลส่งออกตัวอย่าง 2

4 3 3 4 4

ข้อมูลนำเข้าตัวอย่าง 3

6
1 1 2 2 3

ข้อมูลส่งออกตัวอย่าง 3

4 3 5 4 4 6

หมายเหตุ

เพื่ออธิบายกรณีของ $m = 4$ ในตัวอย่างที่ 3: ขั้นแรก ดังที่แสดงในแผนภาพ สมาชิก $m$ ไม่รู้จักสมาชิก $\{3, 5, 6\}$ กลยุทธ์ที่เหมาะสมที่สุดอย่างหนึ่งที่เป็นไปได้คือ ถามก่อนว่า $p$ รู้จักสมาชิก $2$ หรือไม่ ซึ่งมีค่าใช้จ่าย $1$ หากรู้จัก แสดงว่า $p = 5$ และขั้นตอนต่อไปคือถามเกี่ยวกับสมาชิก $5$ เพื่อจบเกม โดยมีค่าใช้จ่ายรวมเป็น $2$ มิฉะนั้น ให้ถามต่อว่า $p$ รู้จักสมาชิก $3$ หรือไม่ ซึ่งมีค่าใช้จ่าย $2$ หาก $p = 3$ เกมจะจบลงด้วยค่าใช้จ่ายรวมเป็น $3$ มิฉะนั้น แสดงว่า $p = 6$ และขั้นตอนต่อไปมีค่าใช้จ่าย $1$ เพื่อถามเกี่ยวกับสมาชิก $6$ ซึ่งจะจบเกมด้วยค่าใช้จ่ายรวมเป็น $4$ ดังนั้น กลยุทธ์นี้จึงใช้ค่าใช้จ่ายในกรณีที่เลวร้ายที่สุดเท่ากับ $4$ สามารถพิสูจน์ได้ว่าไม่มีกลยุทธ์อื่นใดที่สามารถลดค่าใช้จ่ายในการถามในกรณีที่เลวร้ายที่สุดลงได้อีก