Problème
Le motif composite traite les objets simples et les groupes d'objets de la même façon. La taille d'un dossier est la taille de ses propres fichiers plus la taille de tout ce qu'il contient, quelle que soit la profondeur.
Il y a n éléments numérotés de 0 à n − 1 formant un arbre. parents[i] est le dossier qui contient l'élément i, ou -1 pour la racine (un seul élément). sizes[i] est la taille du contenu propre de l'élément i.
Implémentez composite_folder_sizes(parents, sizes).
Input
parents : le parent de chaque élément.
sizes : la taille propre de chaque élément.
Output
Retournez, pour chaque élément, sa taille totale : sa propre taille plus les totaux de tous ses enfants.
Contraintes
1 ≤ n ≤ 100,000
0 ≤ sizes[i] ≤ 10^9 ; parents décrit un seul arbre
Exemples
Entrée :
sizes = [1, 2, 3, 4]
parents = [-1, 0, 0, 1]
Sortie attendue :
expected = [10, 6, 3, 4]Entrée :
std::vector<long long> sizes = {1, 2, 3, 4};
std::vector<long long> parents = {-1, 0, 0, 1};
Sortie attendue :
std::vector<long long> expected = {10, 6, 3, 4};Entrée :
long[] sizes = new long[] {1, 2, 3, 4};
long[] parents = new long[] {-1, 0, 0, 1};
Sortie attendue :
long[] expected = new long[] {10, 6, 3, 4};Explication
L'élément 3 (taille 4) est à l'intérieur de l'élément 1, donc l'élément 1 totalise 2 + 4 = 6. La racine contient les éléments 1 et 2 : 1 + 6 + 3 = 10. Résultat : [10, 6, 3, 4].
Entrée :
sizes = [5, 0, 7]
parents = [1, -1, 1]
Sortie attendue :
expected = [5, 12, 7]Entrée :
std::vector<long long> sizes = {5, 0, 7};
std::vector<long long> parents = {1, -1, 1};
Sortie attendue :
std::vector<long long> expected = {5, 12, 7};Entrée :
long[] sizes = new long[] {5, 0, 7};
long[] parents = new long[] {1, -1, 1};
Sortie attendue :
long[] expected = new long[] {5, 12, 7};Explication
La racine est l'élément 1 sans contenu propre ; elle contient les éléments 0 et 2 : 0 + 5 + 7 = 12.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Le total d'un dossier est sa propre taille plus les totaux de ses enfants.
Indice 2
Traitez les enfants avant les parents, par exemple par profondeur décroissante.
Indice 3
Évitez une récursion profonde sur de longues chaînes ; une pile explicite ou un ordre est plus sûr.
Complexité attendue
temps O(n), espace supplémentaire O(n)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.