Building tree from edges puzzle with performance requirement

Question

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<Tuple> allNodes = new Stack<>();
 List<Integer> input = new ArrayList<>();
 //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() > 0) {
 parent = allNodes.get(iterator++).id;
 while ((index = input.indexOf(parent)) >= 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 > childIndex) { input.remove(childIndex); }
 else { input.remove(index); }
 }
 }
 int[] values = new int[allNodes.size()];
 Tuple currentNode;
 //compute values
 while (allNodes.size() > 1) {
 currentNode = allNodes.pop();
 values[currentNode.parent] += ++values[currentNode.id]+1;
 }
 values[0]++;
 int sum = 0;
 for (int i=0; i<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;
 }
}

• Pavlo: Can you please describe it better. If you get the sum of the nodes, then example 1 should return 9. I ran your program and got 16, so i think that the behavior you need is different from the one you describe
• cactus: @Pavlo Example 1: 3 has default value 1 and no children. Its parent 2 has default value 1 plus the value of its child 3 (1) plus 1, so 2 has value 3. 1 has value 5 and 0 has value 7. Total value is 1+3+5+7=16. Basically every node has value: 1 + (# of children) + (sum of children's values).
• Veedrac: This is equivalent to ∑((node depth) × (# children + 1)), though that isn't any faster to compute.

Answer 1

(削除) 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<Node> children;
 public Node(final int id) {
 this.id = id;
 this.children = new ArrayList<>();
 }
 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() > 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

• cactus: Thanks a lot! Your suggestions along with some further modifications allowed me to achieve the performance needed. I had the nodes store their children in a list and used a hashmap to save the input and the nodes. The value was the calculated via DFS (like here).