3331 - Find Subtree Sizes After Changes (Medium)
Problem Link
https://leetcode.com/problems/find-subtree-sizes-after-changes
Problem Statement
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 subtree 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.
Constraints:
n == parent.length == s.length1 <= n <= 1e50 <= parent[i] <= n - 1for alli >= 1.parent[0] == -1parentrepresents a valid tree.sconsists only of lowercase English letters.
Approach 1: DFS
First, we build children, where contains the original children of node . We also create with every value set to , because each node counts as part of its own subtree.
We explore the original tree using a stack instead of recursion. During this traversal, stores the closest ancestor with each character. When we enter a node , we save in . This is the node’s new parent if a matching ancestor exists; otherwise, it keeps its original parent. We then set so descendants can find this node.
Each node is processed twice: once when entering it and once when leaving it. The expression ~ produces a negative number that marks the leaving step. We push this marker before the children, so all children finish before their parent. When leaving, we restore to its previous value, ensuring nodes in other branches do not mistake for an ancestor.
By the time we leave , contains its final subtree size. We add this value to its new parent, or to its original parent if no matching ancestor exists. This works because the chosen parent is always an original ancestor and therefore finishes later. Since we traverse only the original tree, all parent changes are effectively made simultaneously.
The time complexity is and the space complexity is .
class Solution:
def findSubtreeSizes(self, parent: List[int], s: str) -> List[int]:
n = len(parent)
c = [[] for _ in parent]
for i in range(1, n): c[parent[i]].append(i)
res, prev, lst, st = [1] * n, [-1] * n, {}, [0]
while st:
u = st.pop()
if u >= 0:
prev[u] = lst.get(s[u], -1)
lst[s[u]] = u
st.append(~u)
st.extend(c[u])
else:
u = ~u
lst[s[u]] = prev[u]
p = prev[u] if prev[u] >= 0 else parent[u]
if p >= 0: res[p] += res[u]
return res