class Solution:
def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:
n = len(parents)
ans = [1] * n
if 1 not in nums: return ans
g = defaultdict(list)
for i, p in enumerate(parents):
g[p].append(i)
u, v, now = nums.index(1), nums.index(1), 1
vis = [False] * 100010
while u != -1:
q = deque([w for w in g[u] if w != v])
vis[nums[u]] = True
while q:
tmp = q.popleft()
vis[nums[tmp]] = True
q.extend(g[tmp])
for i in range(now, 100010):
if vis[i] == False:
ans[u] = now = i
break
u, v = parents[u], u
return ans
class Solution:
def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:
if 1 not in nums: return [1] * len(parents)
d_path = defaultdict(list)
for idx, val in enumerate(parents):
if val >= 0: d_path[val].append(idx)
for idx, num in enumerate(nums):
if num == 1: break
note = [0] * len(parents)
visited = [0] * len(parents)
def dfs(pt):
if visited[pt] == 0:
visited[pt] = 1
if nums[pt] - 1 < len(nums): note[nums[pt] - 1] = 1
for new_pt in d_path[pt]:
dfs(new_pt)
res = [1] * len(parents)
tmp_pos = 0
while idx != -1:
dfs(idx)
while tmp_pos < len(nums) and note[tmp_pos] == 1:
tmp_pos += 1
res[idx] = tmp_pos + 1
idx = parents[idx]
return res
/**
* 利用无重复基因值的性质
* 由于没有重复基因，若存在一个节点 x，其基因值为 1，那么从 x 到根这一条链上的所有节点，
* 由于子树包含 x，其 mex均大于 1，而其余不在链上的节点，由于子树不包含 x，故其 mex 均为 1。
* 因此，我们只需要计算在这条链上的节点的 mex 值。
* 我们可以从 x 出发，顺着父节点往根走，同时收集当前子树下的所有基因值，
* 然后再不断自增子树的 mex 直至其不在基因值集合中。
*/
func smallestMissingValueSubtree(parents []int, nums []int) []int {
n := len(parents)
mex := make([]int, n)
for i := range mex {
mex[i] = 1
}
g := make([][]int, n)
for w := 1; w < n; w++ {
v := parents[w]
g[v] = append(g[v], w)
}
inSet := map[int]bool{}
var f func(int)
f = func(v int) {
inSet[nums[v]] = true // 收集基因值
for _, w := range g[v] {
if !inSet[nums[w]] { // 避免重复访问节点
f(w)
}
}
}
// 找到基因值等于 1 的节点 x
x := -1
for i, v := range nums {
if v == 1 {
x = i
break
}
}
// x 顺着父节点往上走
for cur := 2; x >= 0; x = parents[x] {
f(x)
for inSet[cur] {
cur++ // 不断自增直至不在基因值集合中
}
mex[x] = cur
}
return mex
}
