Given a tree-graph with one of the vertices designated as the root, what is the complexity of calculating the number of vertex-pairs $\lbrace u,v \rbrace$ of which $v$ is not nearer to the root than $u$ and $u$ is not a vertex of the path from the root to $v$?


It is of course possible to determine that number in $O(n^2)$ by checking each pair's Lowest Common Ancestor, but is there a way of more directly calculating that number?



Calculating number of vertex-pairs with separate common ancestor
It takes only addition to count the distinct pairs where one is the ancestor of another. Couldn’t you just subtract that from the total number of pairs?


