Building tree from edges puzzle with performance requirement
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