where is the KITTY?

WOOHOO, I DID IT!!! sorry, it just took me that long.

And because I'm still high on success, I will leave some tips for despairing ones. (I also don't understand a thing in the editorial)

Calculating every node-combination in a set is O(n²), so we have to condense the set somehow...

Let's say, we have two nodes, v1 and v2; v is the lowest common ancestor(LCA):

      v
     / \
   ..   ..
   /      \
 v1       v2

The thing we have to calculate is v1*v2*d(v1,v2). d() is distance.

It can be split up like this: v1*d(v1,v)*v2 + v2*d(v2,v)*v1

Now, let's add another node (u is the new LCA):

      u
     /  \
    ..   ..
   / \     \
  ..  v2    v3
 /
v1


v1*v2*d(v1,v2) +
(v1*d(v1,u)+v2*d(v2,u))*v3 + v3*d(v3,u)*(v1+v2)

= v1*v2*d(v1,v2) +
((v1+v2)*d(v2,u)+v1*(depth(v1)-depth(v2)))*v3 + v3*d(v3,u)*(v1+v2)

If v1 and v2 are already processed, the only variables are u and v3. We can replace the rest with constants:

C0 + (C1*d(v2,u)+C2)*v3 + v3*d(u,v3)*C1

...there, it's no longer necessay to handle v1 and v2 seperately. (as long as nothing relevant is below v1 or between v1 and v2)

I also used lookup-tables for depth and predecessor.

Please let me know if something is too confusing.

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

why the task talks about a tree? this is undirected graph, isn't it? root is not defined

At the time of this note, none of the Java solutions (leaderboard) has achieved > 19.2 score. My code is passing tests 0-6, and timing out on the rest. I'm using a variation on Tarjan's Offline LCA algorithm, which I think should be reasonably optimal. Are timings too tight for Java? It looks like most of the successful solutions are in c/c++.