3331. Find Subtree Sizes After Changes
Difficulty: Medium
Topics: Staff, Array, Hash Table, String, Tree, Depth-First Search, Biweekly Contest 142
You are given a tree rooted at node 0 that consists of n nodes numbered from 0 to n - 1. The tree is represented by an array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1.
You are also given a string s of length n, where s[i] is the character assigned to node i.
We make the following changes on the tree one time simultaneously for all nodes x from 1 to n - 1:
- Find the closest node
yto nodexsuch thatyis an ancestor ofx, ands[x] == s[y]. - If node
ydoes not exist, do nothing. - Otherwise, remove the edge between
xand its current parent and make nodeythe new parent ofxby adding an edge between them.
Return an array answer of size n where answer[i] is the size of the subtree1 rooted at node i in the final tree.
Example 1:
- Input: parent = [-1,0,0,1,1,1], s = "abaabc"
- Output: [6,3,1,1,1,1]
-
Explanation:
- 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]
-
Explanation:
- The following changes will happen at the same time:
- The parent of node 4 will change from node 1 to node 0.
- The parent of node 2 will change from node 4 to node 1.
- The following changes will happen at the same time:
Example 3:
- Input: parent = [-1], s = "a"
- Output: [1]
Example 4:
- Input: parent = [-1,0,1,2], s = "aaaa"
- Output: [4,3,2,1]
Example 5:
- Input: parent = [-1,0,1,2], s = "abab"
- Output: [4,2,1,1]
Example 6:
- Input: parent = [-1,0,0,1,1,2], s = "aaaaaa"
- Output: [6,3,2,1,1,1]
Constraints:
n == parent.length == s.length1 <= n <= 10⁵0 <= parent[i] <= n - 1 for all i >= 1.parent[0] == -1-
parentrepresents a valid tree. -
sconsists only of lowercase English letters.
Hint:
- Perform a depth-first search on the tree, starting from the root.
- During the DFS, keep track of the most recent node where each character from
'a'to'z'has been seen.
Solution:
We perform an iterative DFS on the original tree while maintaining, for each character, the most recent node of that character on the current root-to-node path. This lets us find the closest same-character ancestor for every node and build the final parent array in O(n) time. Then we compute subtree sizes by processing nodes in reverse DFS preorder and accumulating sizes into their final parents.
Approach
- Build the original tree’s children adjacency list from
parent. - Use an iterative DFS to avoid recursion depth issues for
nup to10⁵. - Maintain
last[26], wherelast[c]is the most recent node on the current DFS path whose character isc. - When entering node
u:- The closest same-character ancestor is exactly
last[s[u]], if it exists. - If it exists and
u != 0, setnewParent[u]to that ancestor. - Update
last[s[u]] = u.
- The closest same-character ancestor is exactly
- On exiting node
u, restorelast[s[u]]to its previous value so siblings do not incorrectly see nodes outside their path. - After building
newParent, initialize every node’s subtree size to1. - Process nodes in reverse DFS preorder:
- For each node
u, addanswer[u]toanswer[newParent[u]]ifnewParent[u] != -1.
- For each node
Let's implement this solution in PHP: 3331. Find Subtree Sizes After Changes
<?php /** * @param Integer[] $parent * @param String $s * @return Integer[] */ function findSubtreeSizes(array $parent, string $s): array { ... ... ... /** * go to ./solution.php */ } // Test cases echo json_encode(findSubtreeSizes([-1,0,0,1,1,1], "abaabc")) . "\n"; // Output: [6,3,1,1,1,1] echo json_encode(findSubtreeSizes([-1,0,4,0,1], "abbba")) . "\n"; // Output: [5,2,1,1,1] echo json_encode(findSubtreeSizes([-1], "a")) . "\n"; // Output: [1] echo json_encode(findSubtreeSizes([-1,0,1,2], "aaaa")) . "\n"; // Output: [4,3,2,1] echo json_encode(findSubtreeSizes([-1,0,1,2], "abab")) . "\n"; // Output: [4,2,1,1] echo json_encode(findSubtreeSizes([-1,0,0,1,1,2], "aaaaaa")) . "\n"; // Output: [6,3,2,1,1,1] ?> Explanation
- The DFS path represents exactly the ancestor chain of the current node.
-
last[c]stores the nearest ancestor with charactercseen so far. - Therefore, when visiting
u,last[s[u]]is the closest same-character ancestor required by the problem. - The rewiring is “simultaneous,” but this does not cause conflicts because all new parents are determined using only the original tree’s DFS ancestor paths.
- The final tree’s parent of any node is always an ancestor of that node in the original tree.
- In DFS preorder, every ancestor appears before its descendants. Thus, processing nodes in reverse preorder guarantees that a node’s final subtree size is fully computed before adding it to its final parent.
Complexity Analysis
- Time Complexity:
O(n)- Building the tree:
O(n) - Iterative DFS and rewiring:
O(n) - Subtree size accumulation:
O(n)
- Building the tree:
- Space Complexity:
O(n)- Children adjacency list:
O(n) - DFS stack, order array, final parent array, answer array:
O(n) -
last[26]isO(1)extra space.
- Children adjacency list:
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:
-
Subtree: A subtree of
treeNameis a tree consisting of a node intreeNameand all of its descendants. ↩
