Python | O(n log(n)) | LCA
Let v be the node with lowest nums[v] value.  Observe that any node u not in v\'s ancestor chain does not have nums[v] in its subtree, so its answer will be num
Let `v` be the node with lowest `nums[v]` value.  Observe that any node `u` not in `v`\'s ancestor chain does not have `nums[v]` in its subtree, so its answer will be `nums[v]`.  This leads the following algorithm:\n\n1. Find `u` such that `nums[u] = 1`, and store its ancestor chain in a stack `nodes`, with `nodes[-1] = u, nodes[0] = 0`\n2. Assign all nodes not in `nodes` value 1\n3. For `k = 2, 3, ...` find `w = LCA(u, v)` where `u` and `v` are the nodes such that`u = nodes[-1]` and `nums[v] = k`. Assign all nodes from `u -> w` value `k`, excluding `w`\n\n\n```python\nfrom collections import defaultdict, deque\n\n\nclass Solution:\n    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n        n = len(parents)\n        \n        # P[k][u] := u\'s 2^k parent\n        # Used to answer LCA queries\n        P = [list(parents)]\n        while any(x != -1 for x in P[-1]):\n            prev = P[-1]\n            curr = [-1] * n\n            for i in range(n):\n                if prev[i] != -1:\n                    curr[i] = prev[prev[i]]\n            P.append(curr)\n\n        children = defaultdict(list)\n        for i in range(n):\n            children[parents[i]].append(i)\n\n        # Height of the node from the root\n        # Root height = 0\n        # child height = 1 + parent height\n        # BFS\n        heights = [0] * n\n        queue = deque()\n        queue.append(0)\n        while len(queue) > 0:\n            u = queue.popleft()\n            for v in children[u]:\n                heights[v] = heights[u] + 1\n                queue.append(v)\n        \n        # Lowest common ancestor of nodes u and v\n        # Using algorithm described here:\n        # https://web.stanford.edu/class/cs97si/03-data-structures.pdf\n        def lca(u, v):\n            # Bring v up to u\'s height if v is greater height\n            h_u = heights[u]\n            h_v = heights[v]\n            if h_u > h_v:\n                u, v, h_u, h_v = v, u, h_v, h_u\n            if h_u < h_v:\n                d = h_v - h_u\n                d_bin = "{0:b}".format(d)\n                for i in range(len(d_bin)):\n                    if d_bin[i] == \'1\':\n                        k = len(d_bin) - i - 1\n                        v = P[k][v]\n            assert heights[v] == heights[u]\n            for k in reversed(range(len(P))):\n                if P[k][u] != P[k][v]:\n                    u, v = P[k][u], P[k][v]\n            if u == v:\n                return u\n            else:\n                return P[0][u]\n\n        \n        num_to_node = {num: idx for idx, num in enumerate(nums)}\n        if 1 not in num_to_node:\n            return [1] * n\n        # Anything not in 1\'s ancestor chain has an answer of 1\n        u = num_to_node[1]\n        nodes = [u]\n        while parents[nodes[-1]] != -1:\n            nodes.append(parents[nodes[-1]])\n        nodes = list(reversed(nodes))\n        ans = [1] * n\n        \n        # * Find the node v with the next lowest nums value, k\n        # * Find the LCA(u, v) where u is the last node in the chain of nodes\n        # * If LCA(u, v) != u, then k is not in u\'s subtree so assign u value k\n        k = 2\n        while len(nodes) > 0:\n            u = nodes[-1]\n            if k not in num_to_node:\n                break\n            v = num_to_node[k]\n            w = lca(u, v)\n            while u != w:\n                ans[u] = k\n                nodes.pop()\n                u = nodes[-1]\n            k += 1\n        for u in nodes:\n            ans[u] = k\n        return ans\n```
[]