Actually, I guess I have some kind of intuitive explanation behind this. If we imagine that each node "contributes" to the $$$N^2$$$ count, we can observe that no matter how the tree is structured, the total number that it contributes will be maximum $$$N$$$, since once two subtrees "merge" they will no longer multiply within themselves to count towards the $$$N^2$$$. So, since each node will add a maximum of $$$N$$$ towards the count, the total number will add up to maximum $$$N^2$$$. I think I am more interested in formal proof.

Another way to think about it is that any pair of nodes $$$(u, v)$$$ is considered at most (exactly, in fact) once and this happens at their LCA.

Suppose we want to count number of pairs $$$(u, v)$$$ such that $$$LCA(u, v) = i$$$. If children of $$$i$$$ are $$$l$$$ and $$$r$$$, then the number is equal of $$$\text{SubtreeSize}(l) \times \text{SubtreeSize}(r)$$$ if we consider pairs $$$(u, v)$$$ and $$$(v, u)$$$ equal. Therefore the sum you mentioned is equal to total number of pairs of vertices in the tree (number of subsets of size two).

The given sum is same as the union of cross products of sets of vertoces of left and right subtrees. Now we can see that each unordered pair of vertices $$$(u,v)$$$ occurs atmost once in the above union. This also gives an upper bound of $$$N*(N-1)/2$$$

https://codeforces.me/blog/entry/124538?#comment-1105664