Bedao Grand Contest 11 - INVESTIGATION

View as PDF

Submit solution


Points: 1.00 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

lastPledge đang bị truy nã toàn thành phố vì lỡ đánh cắp trái tim của crush! Lúc này, hắn ta đang tìm đường trốn ra nước ngoài, tuy nhiên, vì cả thành phố đều bị phong tỏa, lastPledge đành phải trốn tạm vào một ngôi nhà và án binh bất động để tránh bị cảnh sát tìm thấy.

Thành phố nơi lastPledge đang sống có ~n~ ngôi nhà và ~n - 1~ con đường nối trực tiếp giữa hai căn nhà, sao cho luôn tồn tại đường đi giữa ~2~ ngôi nhà bất kì. Là cảnh sát trưởng của thành phố, FireGhost được giao nhiệm vụ tóm gọn tên trộm. Anh ấy sẽ lặp lại những thao tác sau đến khi bắt được lastPledge:

  • FireGhost sẽ chọn một ngôi nhà bất kì, sau đó lục soát căn nhà để tìm kiếm tên trộm. Quá trình này sẽ mất ~1~ tiếng.

  • Nếu tìm thấy tên trộm, anh ấy sẽ dừng quá trình tìm kiếm và áp giải tên trộm về đồn cảnh sát.

  • Ngược lại, anh ấy sẽ được người dân chỉ điểm: Trong các con đường đi ra khỏi căn nhà hiện tại, con đường nào sẽ dẫn tới nơi tên trộm đang trốn.

Biết rằng FireGhost là một cảnh sát vô cùng thông minh, anh ta luôn chọn phương án tối ưu khi làm việc. Hãy cho biết trong trường hợp xấu nhất anh ta sẽ mất bao nhiêu thời gian để bắt được tên trộm lastPledge.

Input

  • Dòng đầu tiên gồm số nguyên dương ~n~ — số ngôi nhà trong thành phố (~1 \le n \le 10^5~).

  • Dòng tiếp theo gồm ~n - 1~ số nguyên ~p_1, p_2, \ldots, p_{n - 1}~ (~0 \le p_i < i~), thể hiện một con đường nối ~2~ ngôi nhà ~i~ và ~p_i~.

Output

  • In ra số giờ ít nhất cần bỏ ra để bắt được tên trộm trong trường hợp xấu nhất.

Subtask

  • ~16\%~ số test khác có ~n \le 20~.

  • ~36\%~ số test khác có ~n \le 5000~.

  • ~48\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

5
0 1 1 1

Sample Output 1

2

Sample Input 2

8
0 1 2 1 3 5 6

Sample Output 2

3

Notes

Trong test ví dụ đầu tiên, nếu FireGhost không chọn đỉnh ~1~ ở lượt đầu tiên, anh ấy sẽ cần thêm ít nhất ~2~ lượt trong trường hợp xấu nhất.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.