Reference here

Disintegrating the formula

let u and v be the nodes in the tree with LCA(u, v) = L

Let F = u * v * d(v,u)

d(u,v) = d(u,L) + d(L,v)

F = u * v * (d(u,L) + d(L,v))

F = u * v * d(u,L) + u * v * d(L,v)

Let F1 = u * v * d(u, L) and F2 = u * v * d(L,v)

Analysing parts of Formula

Seeing F1 = u * d(u, L) * v

we have to run F1 for all u , v with LCA(u, v) = L

So now if we fix u and L in our tree

then

F1_summation(u, L) = u * d(u, L) * (v1 + v2 + v3....)

F1_summation(x, y) means taking summation on F1 fixing x and y

now the term

(v1 + v2 + v3 ....) = (the sum of all subtrees of L - subtree containing u)

as v1, v2, v3... are all nodes with whom the LCA(u, vi) = L

F1 is same as F2

This is a similar logic for F2 just that we are fixing v and L

(similar to F1 from the perspective of v)

so F1 = F2

and we have to find answer for the set pairs {u, v} so

so F_summation = 2 * F1_summation

Final Answer

Final Answer = F_summation / 2

as we process for {u,v} and {v,u} so we have haved the answer

therefore Final Answer = F1_summation(u,L)

Precomputation and Processing

We can precompute the subtree sum using Post Order Traversal / DFS

For each u in the tree we can have depth D

Number of possible LCA with any node is D (i.e. logN)

there for we take u and any ancestor out of D ancestors of u each time and compute

F1_summation(u,any_ancestor(u)) = u * d(u, any_ancestor(u)) * (v1 + v2 + v3....)

then the problem can be solved in NlogN time complexity