时间戳

首页 > 解决方案 > MEX 从根节点到树中的每个其他节点

java - MEX 从根节点到树中的每个其他节点

问题描述

给定一棵有 N 个节点的有根树。根节点是节点 1。每个第 i 个节点都有一些与之关联的值 val[i]。

对于每个节点 i (1<=i<=N)，我们想知道从根节点到节点 i 的路径值的 MEX。

数组的 MEX 是数组中不存在的最小正整数，例如 {1,2,4} 的 MEX 为 3

示例： 假设我们有 4 个节点的树。节点的值为 [1,3,2,8] 并且我们还有每个节点 i 的父节点（节点 1 除外，因为它是根节点）。在本示例中，父数组定义为 [1,2,2]。这意味着节点2的父节点是节点1，节点3的父节点是节点2，节点4的父节点也是节点2。

Node 1 : MEX(1) = 2
Node 2 : MEX(1,3) = 2
Node 3 : MEX(1,3,2) = 4
Node 4 : MEX(1,3,8) = 2

因此答案是 [2,2,4,2]

在最坏的情况下，节点的总数可以达到 10^6，每个节点的值可以达到 10^9。

试图 ：

方法 1：我们知道 N 个元素的 MEX 总是在 1 到 N+1 之间。我试图用这种理解来解决这个树问题，但是在这种情况下，N 将随着向叶节点前进而继续动态变化。

方法 2：另一个想法是创建一个包含 N+1 个空值的数组，然后尝试从根节点开始填充它们。但随后我面临的挑战是跟踪该数组中的第一个未填充值。

标签： javaarraysalgorithmdata-structurestree

解决方案

public class TestClass {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter wr = new PrintWriter(System.out);
        int T = Integer.parseInt(br.readLine().trim());
        for(int t_i = 0; t_i < T; t_i++)
        {
            int N = Integer.parseInt(br.readLine().trim());
            String[] arr_val = br.readLine().split(" ");
            int[] val = new int[N];
            for(int i_val = 0; i_val < arr_val.length; i_val++)
            {
                val[i_val] = Integer.parseInt(arr_val[i_val]);
            }
            String[] arr_parent = br.readLine().split(" ");
            int[] parent = new int[N-1];
            for(int i_parent = 0; i_parent < arr_parent.length; i_parent++)
            {
                parent[i_parent] = Integer.parseInt(arr_parent[i_parent]);
            }

            int[] out_ = solve(N, val, parent);
            System.out.print(out_[0]);
            for(int i_out_ = 1; i_out_ < out_.length; i_out_++)
            {
                System.out.print(" " + out_[i_out_]);
            }
            
            System.out.println();
            
         }

         wr.close();
         br.close();
    }
    static int[] solve(int N, int[] val, int[] parent){
       // Write your code here
        int[] result = new int[val.length];
        ArrayList<ArrayList<Integer>> temp = new ArrayList<>();
        ArrayList<Integer> curr = new ArrayList<>();

        if(val[0]==1)
            curr.add(2);
        else{
            curr.add(1);
            curr.add(val[0]);
        }
        result[0]=curr.get(0);
        temp.add(new ArrayList<>(curr));
        for(int i=1;i<val.length;i++){

            int parentIndex = parent[i-1]-1;
            curr = new ArrayList<>(temp.get(parentIndex));
            int nodeValue = val[i];
            boolean enter = false;
            while(curr.size()>0 && nodeValue == curr.get(0)){
                curr.remove(0);
                nodeValue++;
                enter=true;
            }
            if(curr.isEmpty())
                curr.add(nodeValue);
            else if(!curr.isEmpty() && curr.contains(nodeValue) ==false && (enter|| curr.get(0)<nodeValue))
                curr.add(nodeValue);

            Collections.sort(curr);
            temp.add(new ArrayList<>(curr));
            result[i]=curr.get(0);
        }

        return result;
    
    }
}

推荐阅读