stupid. Binary Index Tree way
\n\n\nclass BIT {\n    private int[] a;\n    private int n;\n    public BIT(int n) {\n        a = new int[n+1];\n        this.n = n;\n    }\n    public int lowb
```\n\n\nclass BIT {\n    private int[] a;\n    private int n;\n    public BIT(int n) {\n        a = new int[n+1];\n        this.n = n;\n    }\n    public int lowbit(int x) {\n        return x & (-x);\n    }\n    public void update(int key, int v) {\n        while (key <= n) {\n            a[key] += v;\n            key += lowbit(key);\n        }\n    }\n\n    public int query(int x) {\n        int ans = 0;\n        while (x > 0) {\n            ans += a[x];\n            x -= lowbit(x);\n        }\n        return ans;\n    }\n\n    public int query_by_range(int l, int r) {\n        if (l <= 1) {\n            return query(r);\n        }\n        return query(r) - query(l - 1);\n    }\n\n}\n\nclass Solution {\n    private void find_max_min(HashMap<Integer, ArrayList<Integer>> nxt, int r, int[] ma, int[] mi, int[] nums) {\n        ma[r] = nums[r];\n        mi[r] = nums[r];\n        if (nxt.containsKey(r)) {\n            for(int j:nxt.get(r)) {\n                find_max_min(nxt, j, ma, mi, nums);\n                ma[r] = Math.max(ma[r], ma[j]);\n                mi[r] = Math.min(mi[r], mi[j]);\n            }\n        }\n    }\n\n    private int query_first_1(BIT m_bit, int l, int r) {\n        int mid = 0, v=0;\n        while (l <= r) {\n            mid = (l + r) /2;\n            v = m_bit.query_by_range(l, mid);\n            if (v > 0) {\n                r = mid - 1;\n            } else {\n                l = mid + 1;\n            }\n        }\n        return l;\n    }\n\n    private int query_first_0(BIT m_bit, int l, int r) {\n        int mid = 0, v=0;\n        while (l <= r) {\n            mid = (l + r) /2;\n            v = m_bit.query_by_range(l, mid);\n            if (v != mid - l + 1) {\n                r = mid - 1;\n            } else {\n                l = mid + 1;\n            }\n        }\n        return l;\n    }\n\n    private void dfs(HashMap<Integer, ArrayList<Integer>> nxt, int r, int[] ma, int[] mi, int[] nums, int[] ans, BIT m_bit) {\n        if (nxt.containsKey(r)) {\n            for(int j:nxt.get(r)) {\n                int minJ = mi[j];\n                int maxJ = ma[j];\n                if (minJ > 1) {\n                    ans[j] = 1;\n                    dfs(nxt, j, ma, mi, nums, ans, m_bit);\n                } else {\n                    int candi = query_first_1(m_bit, minJ, maxJ);\n                    dfs(nxt, j, ma, mi, nums, ans, m_bit);\n                    int candi2 = query_first_0(m_bit, minJ, candi - 1);\n                    ans[j] = candi2;\n                }\n            }\n        }\n        m_bit.update(nums[r], 1);\n    }\n\n\n    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {\n        HashMap<Integer, ArrayList<Integer>> nxt = new HashMap<>();\n        int n = nums.length;\n        int[] ma = new int[n];\n        int[] mi = new int[n];\n        for(int i = 1; i < parents.length; ++i) {\n            nxt.computeIfAbsent(parents[i], x -> new ArrayList<>()).add(i);\n        }\n        find_max_min(nxt, 0, ma, mi, nums);\n        int[] ans = new int[n];\n        BIT m_bit = new BIT(100000);\n        dfs(nxt, 0, ma, mi, nums, ans, m_bit);\n        if (mi[0] > 1) {\n            ans[0] = 1;\n        } else {\n            ans[0] = query_first_0(m_bit,1, 100000);\n        }\n        return ans;\n    }\n\n//    public static void main(String args[]) {\n//        Solution2003 so = new Solution2003();\n//        System.out.println(so.smallestMissingValueSubtree(new int[]{-1,0,0,2}, new int[]{1,2,3,4}));\n//    }\n}\n```
[]