#3331

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find Subtree Sizes After Changes

Calculate the sizes of all subtrees after simultaneous parent changes using array scanning and hash-based counting efficiently.

array hash table string tree depth first search

Problem Statement

Given a tree rooted at node 0 with n nodes numbered from 0 to n - 1, the tree is represented by an array parent where parent[i] is the parent of node i, and parent[0] == -1. Each node also has a character assigned from string s of length n, where s[i] is the character for node i.

Perform simultaneous updates to the tree for all nodes x from 1 to n - 1 according to specific rules, then calculate the size of each node's subtree based on the updated tree structure. Return an array where each element represents the size of the corresponding node's subtree after these changes.

Examples

Example 1

Input: parent = [-1,0,0,1,1,1], s = "abaabc"

Output: [6,3,1,1,1,1]

The parent of node 3 will change from node 1 to node 0.

Example 2

Input: parent = [-1,0,4,0,1], s = "abbba"

Output: [5,2,1,1,1]

The following changes will happen at the same time:

Constraints

n == parent.length == s.length
1 <= n <= 105
0 = 1.
parent[0] == -1
parent represents a valid tree.
s consists only of lowercase English letters.

Solution Approach

Build Tree and Adjacency Mapping

Convert the parent array into an adjacency list to represent children for each node. This allows efficient traversal of the tree when calculating subtree sizes and supports the simultaneous update of parent nodes.

Depth-First Search with Character Counts

Perform a DFS starting from the root node, maintaining a hash map to count character frequencies in each subtree. Combine counts from children to compute subtree sizes accurately while considering character assignments.

Apply Updates Simultaneously and Compute Subtree Sizes

Simulate the changes to parent links for all non-root nodes at once, then recalculate subtree sizes using the DFS and hash-based aggregation. This prevents intermediate miscounts and ensures consistent results across the entire tree.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each node is visited once during DFS and hash updates. Space complexity is O(n) for the adjacency list and hash maps storing character counts for each subtree.

What Interviewers Usually Probe

Expect candidates to identify adjacency list conversion for parent array.
Look for correct DFS traversal and aggregation logic per subtree.
Check handling of simultaneous parent changes without intermediate errors.

Common Pitfalls or Variants

Common pitfalls

Updating subtree sizes incrementally can lead to incorrect counts due to simultaneous changes.
Using only the parent array without adjacency mapping may cause inefficient traversal.
Ignoring character aggregation when computing subtree sizes leads to wrong results.

Follow-up variants

Compute subtree sums based on numeric node values instead of character frequencies.
Handle dynamic insertion or deletion of nodes and recalculate subtree sizes.
Find the largest subtree satisfying a certain character or numeric condition after updates.

FAQ

What is the main approach for Find Subtree Sizes After Changes?

Use array scanning to build the tree structure and hash maps during DFS to track subtree sizes, then apply simultaneous parent updates.

Why is a hash map necessary in this problem?

Hash maps track character counts per subtree efficiently, preventing repeated scans of child nodes for aggregation.

Can DFS handle trees with over 100000 nodes?

Yes, a well-implemented DFS with adjacency lists and hash maps runs in O(n) time and O(n) space for trees up to 10^5 nodes.

What common mistakes occur in this problem?

Incrementally updating parent nodes or ignoring character counts can result in incorrect subtree sizes after changes.

How does the array scanning plus hash lookup pattern apply here?

Array scanning builds the adjacency list quickly, and hash lookups maintain subtree counts, making updates and DFS efficient.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def findSubtreeSizes(self, parent: List[int], s: str) -> List[int]:
        def dfs(i: int, fa: int):
            ans[i] = 1
            d[s[i]].append(i)
            for j in g[i]:
                dfs(j, i)
            k = fa
            if len(d[s[i]]) > 1:
                k = d[s[i]][-2]
            if k != -1:
                ans[k] += ans[i]
            d[s[i]].pop()

        n = len(s)
        g = [[] for _ in range(n)]
        for i in range(1, n):
            g[parent[i]].append(i)
        d = defaultdict(list)
        ans = [0] * n
        dfs(0, -1)
        return ans

Continue Practicing

#3327 check if dfs strings are palindromes #3425 longest special path #3486 longest special path ii