Đề bài
Mẫu thiết kế composite xem các đối tượng đơn lẻ và các nhóm đối tượng theo cùng một cách. Kích thước của một thư mục là tổng kích thước của các tệp riêng của nó cộng với kích thước của mọi thứ bên trong nó, مهما sâu đến đâu.
Có n mục được đánh số từ 0 đến n − 1 tạo thành một cây. parents[i] là thư mục chứa mục i, hoặc -1 nếu là gốc (chỉ có đúng một mục). sizes[i] là kích thước phần nội dung riêng của mục i.
Hãy cài đặt composite_folder_sizes(parents, sizes).
Input
parents: Mục cha của mỗi mục.
sizes: Kích thước riêng của mỗi mục.
Output
Trả về, cho mỗi mục, kích thước tổng của nó: kích thước riêng cộng với tổng kích thước của tất cả các con của nó.
Ràng buộc
1 ≤ n ≤ 100,000
0 ≤ sizes[i] ≤ 10^9; parents mô tả đúng một cây
Ví dụ
Đầu vào:
sizes = [1, 2, 3, 4]
parents = [-1, 0, 0, 1]
Kết quả mong đợi:
expected = [10, 6, 3, 4]Đầu vào:
std::vector<long long> sizes = {1, 2, 3, 4};
std::vector<long long> parents = {-1, 0, 0, 1};
Kết quả mong đợi:
std::vector<long long> expected = {10, 6, 3, 4};Đầu vào:
long[] sizes = new long[] {1, 2, 3, 4};
long[] parents = new long[] {-1, 0, 0, 1};
Kết quả mong đợi:
long[] expected = new long[] {10, 6, 3, 4};Giải thích
Mục 3 (kích thước 4) nằm bên trong mục 1, nên mục 1 có tổng là 2 + 4 = 6. Gốc chứa các mục 1 và 2: 1 + 6 + 3 = 10. Kết quả: [10, 6, 3, 4].
Đầu vào:
sizes = [5, 0, 7]
parents = [1, -1, 1]
Kết quả mong đợi:
expected = [5, 12, 7]Đầu vào:
std::vector<long long> sizes = {5, 0, 7};
std::vector<long long> parents = {1, -1, 1};
Kết quả mong đợi:
std::vector<long long> expected = {5, 12, 7};Đầu vào:
long[] sizes = new long[] {5, 0, 7};
long[] parents = new long[] {1, -1, 1};
Kết quả mong đợi:
long[] expected = new long[] {5, 12, 7};Giải thích
Gốc là mục 1 và không có nội dung riêng; nó chứa các mục 0 và 2: 0 + 5 + 7 = 12.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Tổng của một thư mục là kích thước của nó cộng tổng của các con.
Gợi ý 2
Xử lý con trước cha, ví dụ theo thứ tự độ sâu giảm dần.
Gợi ý 3
Tránh đệ quy sâu trên chuỗi dài; dùng stack hoặc thứ tự duyệt rõ ràng sẽ an toàn hơn.
Độ phức tạp mong đợi
thời gian O(n), bộ nhớ phụ O(n)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.