Паттерн composite рассматривает одиночные объекты и группы объектов одинаково. Размер папки — это размер её собственных файлов плюс размеры всего, что находится внутри неё, на любой глубине.
Есть n элементов, пронумерованных от 0 до n − 1, которые образуют дерево. parents[i] — это папка, содержащая элемент i, или -1 для корня (ровно один элемент). sizes[i] — это размер собственного содержимого элемента i.
Реализуйте composite_folder_sizes(parents, sizes).
Input
parents: Родитель каждого элемента.
sizes: Собственный размер каждого элемента.
Output
Верните для каждого элемента его общий размер: его собственный размер плюс суммы размеров всех его дочерних элементов.
Ограничения
1 ≤ n ≤ 100,000
0 ≤ sizes[i] ≤ 10^9; parents описывает одно дерево
Примеры
Ввод:
sizes = [1, 2, 3, 4]
parents = [-1, 0, 0, 1]
Ожидаемый вывод:
expected = [10, 6, 3, 4]Ввод:
std::vector<long long> sizes = {1, 2, 3, 4};
std::vector<long long> parents = {-1, 0, 0, 1};
Ожидаемый вывод:
std::vector<long long> expected = {10, 6, 3, 4};Ввод:
long[] sizes = new long[] {1, 2, 3, 4};
long[] parents = new long[] {-1, 0, 0, 1};
Ожидаемый вывод:
long[] expected = new long[] {10, 6, 3, 4};Пояснение
Элемент 3 (size 4) находится внутри элемента 1, поэтому итог для элемента 1 равен 2 + 4 = 6. Корень содержит элементы 1 и 2: 1 + 6 + 3 = 10. Результат: [10, 6, 3, 4].
Ввод:
sizes = [5, 0, 7]
parents = [1, -1, 1]
Ожидаемый вывод:
expected = [5, 12, 7]Ввод:
std::vector<long long> sizes = {5, 0, 7};
std::vector<long long> parents = {1, -1, 1};
Ожидаемый вывод:
std::vector<long long> expected = {5, 12, 7};Ввод:
long[] sizes = new long[] {5, 0, 7};
long[] parents = new long[] {1, -1, 1};
Ожидаемый вывод:
long[] expected = new long[] {5, 12, 7};Пояснение
Корень — это элемент 1 без собственного содержимого; он содержит элементы 0 и 2: 0 + 5 + 7 = 12.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Сумма папки — её собственный размер плюс суммы детей.
Подсказка 2
Обрабатывайте детей раньше родителей, например по убыванию глубины.
Подсказка 3
Избегайте глубокой рекурсии на длинных цепочках; явный стек или порядок надёжнее.
Ожидаемая сложность
время O(n), доп. память O(n)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.