Mã bài:
capoostree
Điểm:
4 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Dữ liệu vào:
stdin
Dữ liệu ra:
stdout
Tác giả:
Dạng bài
Mèo ~Capoo~ rất thích sơn màu lên chiếc cây sau vườn hàng xóm của mình. Cây của ~Capoo~ được miêu tả là một đồ thị vô hướng liên thông không có thu trình, gồm ~n~ đỉnh đánh số từ ~0~ đến ~n - 1~.
Khoảng cách giữa ~2~ đỉnh được đo bằng số cạnh trên đường đi giữa chúng.
Đỉnh ~i~ sau khi tô màu sẽ tăng vẻ đẹp của cây lên ~a_i~.
~Capoo~ không muốn để hàng xóm cậu ấy phát hiện, cậu ta đã nghĩ ra ~1~ cách chính là tô màu các đỉnh cách nhau một khoảng lớn hơn ~k~ để cái cây không trở nên rực rỡ. Nhiệm vụ của bạn là giúp ~Capoo~ tìm tập đỉnh sao cho chiếc cây có vẻ đẹp lớn nhất mà vẫn tránh được hàng xóm của cậu phát hiện ra.
Dữ liệu vào
- Dòng thứ nhất gồm ~2~ số nguyên dương ~n~ và ~k~ (~n \le 5\times 10^5~ và ~1 \le k \le 2\times 10^5~).
- Dòng thứ hai gồm ~n~ số nguyên dương ~a_i~ (~a_i \le 10^4~).
- ~n - 1~ dòng tiếp theo, dòng thứ ~i~ chứa một số nguyên dương ~x_i~ - có cạnh nối giữa đỉnh ~x_i~ và đỉnh ~i~ (~0 \le x_i < i~).
Dữ liệu ra
Gồm một số nguyên duy nhất - số đỉnh lớn nhất ~Capoo~ có thể tô màu thỏa điều kiện.
Ràng buộc
- Subtask 1 ~(12\%):~ ~n \le 18~.
- Subtask 2 ~(16\%):~ ~n \le 400~.
- Subtask 3 ~(12\%):~ ~n \le 5000~.
- Subtask 4 ~(16\%):~ ~n \le 5\times 10^5~ và mỗi đỉnh có không quá ~2~ cạnh nối.
- Subtask 5 ~(32\%):~ ~n \le 5\times 10^5~.
Ví dụ
Dữ liệu
8 1
10 2 3 3 4 2 1 5
0
1
0
3
2
2
1
Kết quả
22
Giải thích
Chọn tập các đỉnh ~0, 2, 4, 7~.
Bình luận