Problema
El patrón composite trata a los objetos individuales y a los grupos de objetos de la misma manera. El tamaño de una carpeta es la suma de sus propios archivos más los tamaños de todo lo que contiene, sin importar la profundidad.
Hay n elementos numerados de 0 a n − 1 que forman un árbol. parents[i] es la carpeta que contiene el elemento i, o -1 para la raíz (exactamente un elemento). sizes[i] es el tamaño del propio contenido del elemento i.
Implementa composite_folder_sizes(parents, sizes).
Entrada
parents: El padre de cada elemento.
sizes: El tamaño propio de cada elemento.
Salida
Devuelve, para cada elemento, su tamaño total: su tamaño propio más los totales de todos sus hijos.
Restricciones
1 ≤ n ≤ 100,000
0 ≤ sizes[i] ≤ 10^9; parents describe un único árbol
Ejemplos
Entrada:
sizes = [1, 2, 3, 4]
parents = [-1, 0, 0, 1]
Salida esperada:
expected = [10, 6, 3, 4]Entrada:
std::vector<long long> sizes = {1, 2, 3, 4};
std::vector<long long> parents = {-1, 0, 0, 1};
Salida esperada:
std::vector<long long> expected = {10, 6, 3, 4};Entrada:
long[] sizes = new long[] {1, 2, 3, 4};
long[] parents = new long[] {-1, 0, 0, 1};
Salida esperada:
long[] expected = new long[] {10, 6, 3, 4};Explicación
El elemento 3 (tamaño 4) está dentro del elemento 1, así que el total de 1 es 2 + 4 = 6. La raíz contiene los elementos 1 y 2: 1 + 6 + 3 = 10. Resultado: [10, 6, 3, 4].
Entrada:
sizes = [5, 0, 7]
parents = [1, -1, 1]
Salida esperada:
expected = [5, 12, 7]Entrada:
std::vector<long long> sizes = {5, 0, 7};
std::vector<long long> parents = {1, -1, 1};
Salida esperada:
std::vector<long long> expected = {5, 12, 7};Entrada:
long[] sizes = new long[] {5, 0, 7};
long[] parents = new long[] {1, -1, 1};
Salida esperada:
long[] expected = new long[] {5, 12, 7};Explicación
La raíz es el elemento 1, sin contenido propio; contiene los elementos 0 y 2: 0 + 5 + 7 = 12.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
El total de una carpeta es su propio tamaño más los totales de sus hijos.
Pista 2
Procesa los hijos antes que los padres, por ejemplo por profundidad decreciente.
Pista 3
Evita la recursión profunda en cadenas largas; una pila explícita o un orden es más seguro.
Complejidad esperada
tiempo O(n), espacio extra O(n)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.