📖 Bài giảng & lời giải: đây là Bài tập 4 trong bài giảng Thuật toán qua trò chơi 5: Cờ caro trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Cho cây có $n$ nút, gốc là nút 1, cha của nút $i$ ($2 \le i \le n$) là $p_i$ với $p_i \lt i$. Mỗi lá (nút không có con) có một số điểm $a_i$. Một quân cờ đặt ở gốc; An và Bình lần lượt di chuyển quân cờ từ nút hiện tại xuống một nút con của nó, An đi trước. Khi quân cờ tới một lá thì trò chơi kết thúc và An nhận đúng số điểm ghi ở lá đó. An muốn điểm lớn nhất, Bình muốn điểm nhỏ nhất. Hỏi An được bao nhiêu điểm nếu cả hai đều chơi tối ưu?

(Nếu $n = 1$ thì gốc cũng là lá, trò chơi kết thúc ngay và An nhận $a_1$.)

Dữ liệu vào

• Dòng 1: số nguyên $n$ ($1 \le n \le 2 \cdot 10^5$).
• Dòng 2: $n - 1$ số nguyên $p_2, p_3, \ldots, p_n$ ($1 \le p_i \lt i$); dòng này rỗng nếu $n = 1$.
• Dòng 3: $n$ số nguyên $a_1, a_2, \ldots, a_n$ ($|a_i| \le 10^9$); với nút không phải lá thì $a_i = 0$ và không được dùng tới.

Kết quả

In ra số điểm An nhận được.

Sample Input

7
1 1 2 2 3 3
0 0 0 3 5 2 9

Sample Output

3