Distance Code

/*
NAME: William Bille Meyling
EVENT: NOI 2019
DATE: 6/3-2019
 */

/*Initial thoughts
    thinking depth first with iterative deepening maybe (though slow)
    using heap for encode?
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;

public class Distance_Code_Done {

    private static boolean[] visited;

    //could merge these classes or extend from another.
    private static class Node{
        int number;
        HashSet<Node> nbs = new HashSet<>();
        Node parent = null;
        public Node(int number){
            this.number = number;
        }
    }

    private static class Node2{
        int number;
        ArrayList<Node2> node_child = new ArrayList<>();
        Node2 parent;
        public Node2(int number){
            this.number = number;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int type = Integer.valueOf(br.readLine());
        int N = Integer.valueOf(br.readLine());
        if(type == 1){
            ArrayList<Node> nodes = new ArrayList<>();
            for(int i = 0; i < N; i++) nodes.add(null);
            for(int i = 0; i < N - 1; i++){
                String[] input = br.readLine().split(" ");
                int a = Integer.valueOf(input[0])-1;
                int b = Integer.valueOf(input[1])-1;
                if(nodes.get(a) == null){
                    nodes.set(a, new Node(a));
                }
                if(nodes.get(b) == null) {
                    nodes.set(b, new Node(b));
                }
                nodes.get(a).nbs.add(nodes.get(b));
                nodes.get(b).nbs.add(nodes.get(a));
            }
            Node start = nodes.get(0);
            visited = new boolean[N+1];
            visited[start.number] = true;
            build(start);
            dfs_enh(start);
        }else{
            inputs = br.readLine().split(" ");
            Node2 startNode = new Node2(nextNumber);
            decode(startNode);
        }
    }

    private static void dfs_enh(Node node){
        if(node.nbs.size() == 0){
            System.out.print((node.number+1) + " ");
            node.parent.nbs.remove(node);
            return;
        }
        ArrayList<Node> children = new ArrayList<>(node.nbs);
        for(int i = children.size()-1; i > -1; i--){
            dfs_enh(children.get(i));
        }
        System.out.print((node.number+1) + " ");
    }

    private static void build(Node node){
        node.nbs.remove(node.parent);
        for(Node n : node.nbs){
            n.parent = node;
            build(n);
        }
    }

    private static int nextNumber = 1;
    private static String[] inputs;

    private static void decode(Node2 node){
        Node2 current = node;
        for(int i = 0; i < inputs.length; i++){
            //micro optimization: save inputs[i] value as int before
            int diff = Integer.valueOf(inputs[i]);
            if(current.parent == null){
                nextNumber++;
                current.parent = new Node2(nextNumber);
                current.parent.node_child.add(current);
            }
            current = current.parent;
            for(int j = 1; j < diff; j++){
                nextNumber++;
                Node2 newNode = new Node2(nextNumber);
                newNode.parent = current;
                current.node_child.add(newNode);
                current = newNode;
            }
        }
        traverse(current);
    }

    private static void traverse(Node2 node){
        for(int i = 0; i < node.node_child.size(); i++){
            System.out.println(node.number + " " + node.node_child.get(i).number);
            traverse(node.node_child.get(i));
        }
    }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

Test 11

Group: 1, 2, 3

Verdict: ACCEPTED

Test 12

Group: 2, 3

Verdict: ACCEPTED

Test 13

Group: 2, 3

Verdict: ACCEPTED

Test 14

Group: 2, 3

Verdict: ACCEPTED

Test 15

Group: 2, 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 1, 2, 3

Verdict: ACCEPTED