Building tree from edges puzzle with performance requirement I'm working on a puzzle and have solved it, but my code is not fast enough to get the maximum score (if the code is faster than a certain achievable threshold, one gets awarded the maximum score). I have tried multiple approaches but it seems I can't figure it out. My Java code is appended at the end.  

The puzzle is as follows: Input is a number >= 1 of lines of two integers separated by a space which represent edges in a graph. This graph is a tree with 0 as root. We have to calculate the "value" of the graph defined as:
Each node initially has value 1. If a node has children, they each increase its value by their value +1. The final value of a node it its new value + values of all it's children. So:

node value =  1 + (# of children) + (sum of children's values). 


The value of the graph is the sum of values of its nodes.
Then print the value modulo 1234567.

Examples:

0 1  
2 1  
2 3  


has value 16.

1 0  
2 0  
1 3  
1 4  


has value 17.

Here's my code, if someone has any idea where I'm being inefficient, thanks for the help!

public static void main (String[] args) {

    Scanner stdin = new Scanner(System.in);
    Stack&lt;Tuple&gt; allNodes = new Stack&lt;&gt;();
    List&lt;Integer&gt; input = new ArrayList&lt;&gt;();

    //add all input to input list
    while (stdin.hasNext()) {
        input.add(stdin.nextInt());
    }

    allNodes.push(new Tuple(0, -1));
    int index, childIndex, child, parent, iterator = 0;

    //search input for known nodes from parents and add them to allNodes
    while (input.size() &gt; 0) {
        parent = allNodes.get(iterator++).id;
        while ((index = input.indexOf(parent)) &gt;= 0) {
            //check whether index is even or odd
            childIndex = (index%2 == 0) ? index+1 : index-1;
            child = input.get(childIndex);

            allNodes.push(new Tuple(child, parent));

            input.remove(index);
            if (index &gt; childIndex) { input.remove(childIndex); }
            else { input.remove(index); }
        }
    }

    int[] values = new int[allNodes.size()];
    Tuple currentNode;

    //compute values
    while (allNodes.size() &gt; 1) {
        currentNode = allNodes.pop();
        values[currentNode.parent] += ++values[currentNode.id]+1;
    }
    values[0]++;

    int sum = 0;
    for (int i=0; i&lt;values.length; i++) {
        sum += values[i];
    }

    System.out.println(sum%1234567);
    stdin.close();
}

public static class Tuple {

    int id;
    int parent;

    public Tuple (int id, int parent) {
        this.id = id;
        this.parent = parent;
    }
}
Would rather make this a comment, but I need 50 reputation for that, so:
It became quite an answer apparently.

I find given code quite confusing. From what I am picking up, it does excessive searching/iteration where it is not necessary. I'd propose to make a refactoring, creating a class representing your tree. Then you can cleanely implement your requirements. E.g.:

public class Node {

    private final int id;
    private final List&lt;Node&gt; children;

    public Node(final int id) {
        this.id = id;
        this.children = new ArrayList&lt;&gt;();
    }

    public void addChild(final Node child) {
        children.add(child);
    }
}


Now you can add some methods directly expressing your requirements:

    public int graphValue() {
        return nodeValue() + children.stream().collect(summingInt(Node::graphValue));
    }

    public int nodeValue() {
        return 1 + children.size() + children.stream().collect(summingInt(Node::nodeValue));
    }


When creating your tree, you could use something like a HashMap so you can retrieve an already existing node by id in constant time. Perhaps you might need more optimizations.

Some other comments:


Try to avoid using the Stack class: see Stack JavaDoc
Close the scanner as soon as possible; it is also AutoCloseable, so you can use try-with-resources: see try-with-resources documentation
Prefer !list.isEmpty() over list.size() &gt; 0, it is more idiomatic and potentially more efficient. Some implementations might traverse all elements to calculate the size, but as soon as there is an element it is of course not empty.
You created a Tuple class, which is a generic thing. But the implementation is not generic. I'd give it a more specific and telling name. (or possibly make it truly generic)
The amount of +'s in values[currentNode.parent] += ++values[currentNode.id] + 1 is too damn high :D