Calculating number of vertex-pairs with separate common ancestor 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?
 A: 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?
A: In the article Sums of powers of the degrees of a graph one finds for the sum of squared vertex degrees the formula
$\sum_2(G)\le e\left(\frac{e}{n-1}+n-2\right);\ e:=\mathrm{card}(E),\ n := \mathrm{card}(V)$
Now in a rooted tree the number of vertex pairs we are looking for can be determined via
$\sum\limits_{v\in V}\sum\limits_{\lbrace s_{vi},\,s_{vj}\rbrace \subseteq S_v}\left|s_{vi}\right|\cdot \left|s_{vj}\right|$  where $s_{vi}$ denotes the siblings of the $i$-th child of vertex $v$ and includes that child.
which amounts to
$\sum\limits_{v\in V}\binom{\mathrm{deg}(v)-1}{2}$
multiplications.
From $$\frac{\binom{\mathrm{deg}-1}{2}}{\mathrm{deg}^2}\ =\ \frac{(\mathrm{deg}-1)(\mathrm{deg}-1)}{2\cdot\mathrm{deg}^2}\approx \frac{1}{2}$$
it follows that the number of operations is bound from above by $$\frac{e\left(\frac{e}{n-1}+n-2\right)}{2}$$
in the case of trees we have $e=n-1$ and thus $\frac{(n-1)^2}{2}$ multiplications
Edit:
while I first thought that Aaron's suggestion to subtract the number of vertex pairs $(u,v)$, with $\mathrm{LCA}(u,v)\in\lbrace u, v\rbrace$ from the number $\frac{n(n-1)}{2}$ of all vertex pairs wouldn't improve the complexity of calculating the number of vertex pairs $(u,v)$ with $\mathrm{LCA}(u,v)\notin\lbrace u, v\rbrace$, it actually is the key to an algorithm requiring only $O(n)$ additions: maintain in e.g. a depth first tree traversal a vertices' number of edges on the path to the root and add that distance to the sum of $\mathrm{LCA}(u,v)\in\lbrace u, v\rbrace$.
