You are viewing a single comment's thread. Return to all comments →
Reference here
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)
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
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 = 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)
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
Seems like cookies are disabled on this browser, please enable them to open this website
Kitty's Calculations on a Tree
You are viewing a single comment's thread. Return to all comments →
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