समस्या
The composite pattern treats single objects and groups of objects the same way. A folder's size is its own files plus the sizes of everything inside it, however deep.
There are n items numbered 0 to n − 1 forming a tree. parents[i] is the folder that contains item i, or -1 for the root (exactly one item). sizes[i] is the size of item i's own content.
Implement composite_folder_sizes(parents, sizes).
Input
parents: The parent of each item.
sizes: The own size of each item.
Output
Return, for every item, its total size: its own size plus the totals of all its children.
सीमाएँ
1 ≤ n ≤ 100,000
0 ≤ sizes[i] ≤ 10^9; parents describe a single tree
उदाहरण
इनपुट:
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};व्याख्या
Item 3 (size 4) is inside item 1, so item 1 totals 2 + 4 = 6. The root holds items 1 and 2: 1 + 6 + 3 = 10. Result: [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};व्याख्या
The root is item 1 with no content of its own; it contains items 0 and 2: 0 + 5 + 7 = 12.
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
A folder's total is its own size plus its children's totals.
संकेत 2
Process children before parents, for example in reverse depth order.
संकेत 3
Avoid deep recursion on long chains; an explicit stack or ordering is safer.
अपेक्षित जटिलता
O(n) time, O(n) extra space
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।