Độ khó: Khó (4/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ 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 bấm vào xem bà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

---

Bài toán gốc trên LeetCode yêu cầu viết hàm; ở đây đã chuyển sang dạng đọc dữ liệu từ bàn phím và in ra màn hình.

Có một cây gia phả có gốc là nút ~0~, gồm ~n~ nút được đánh số từ ~0~ đến ~n - 1~. Cho mảng số nguyên parents (đánh số từ 0), trong đó parents[i] là cha của nút ~i~. Vì nút ~0~ là gốc nên parents[0] == -1.

Có ~10^5~ giá trị gen, mỗi giá trị được biểu diễn bằng một số nguyên trong đoạn ~[1, 10^5]~ (tính cả hai đầu). Cho mảng số nguyên nums (đánh số từ 0), trong đó nums[i] là giá trị gen của nút ~i~, các giá trị này đôi một khác nhau.

Yêu cầu: với mỗi nút ~i~, tìm ans[i] là giá trị gen nhỏ nhất bị thiếu trong cây con có gốc tại nút ~i~.

Cây con có gốc tại nút ~x~ gồm nút ~x~ và tất cả các nút con cháu của nó.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~n~.
• Dòng thứ hai chứa ~n~ số nguyên parents[0], parents[1], ..., parents[n-1].
• Dòng thứ ba chứa ~n~ số nguyên nums[0], nums[1], ..., nums[n-1].

Kết quả

• Một dòng gồm ~n~ số nguyên ans[0], ans[1], ..., ans[n-1], cách nhau bởi dấu cách.

Giới hạn

• ~2 \le n \le 10^5~
• ~0 \le~ parents[i] ~\le n - 1~ với ~i \ne 0~
• parents[0] == -1
• parents biểu diễn một cây hợp lệ.
• ~1 \le~ nums[i] ~\le 10^5~
• Các nums[i] đôi một khác nhau.

Sample Input 1

4
-1 0 0 2
1 2 3 4

Sample Output 1

5 1 1 1

Giải thích

Đáp án cho từng cây con như sau:

• 0: cây con gồm các nút [0,1,2,3] với các gen [1,2,3,4]. Giá trị nhỏ nhất bị thiếu là 5.
• 1: cây con chỉ gồm nút 1 với gen 2. Giá trị nhỏ nhất bị thiếu là 1.
• 2: cây con gồm các nút [2,3] với các gen [3,4]. Giá trị nhỏ nhất bị thiếu là 1.
• 3: cây con chỉ gồm nút 3 với gen 4. Giá trị nhỏ nhất bị thiếu là 1.

Sample Input 2

6
-1 0 1 0 3 3
5 4 6 2 1 3

Sample Output 2

7 1 1 4 2 1

Giải thích

• 0: cây con gồm các nút [0,1,2,3,4,5] với các gen [5,4,6,2,1,3]. Giá trị nhỏ nhất bị thiếu là 7.
• 1: cây con gồm các nút [1,2] với các gen [4,6]. Giá trị nhỏ nhất bị thiếu là 1.
• 2: cây con chỉ gồm nút 2 với gen 6. Giá trị nhỏ nhất bị thiếu là 1.
• 3: cây con gồm các nút [3,4,5] với các gen [2,1,3]. Giá trị nhỏ nhất bị thiếu là 4.
• 4: cây con chỉ gồm nút 4 với gen 1. Giá trị nhỏ nhất bị thiếu là 2.
• 5: cây con chỉ gồm nút 5 với gen 3. Giá trị nhỏ nhất bị thiếu là 1.

Sample Input 3

7
-1 2 3 0 2 4 1
2 3 4 5 6 7 8

Sample Output 3

1 1 1 1 1 1 1

Giải thích

Giá trị 1 bị thiếu trong tất cả các cây con.

Nguồn: LeetCode 2003.