I recently saw a problem in some online judge where I was given a tree and was asked the value of Σ f(u, v) for all pair of u, v where f is some function that takes two nodes u, v of a graph. for example f(u, v) can be any of these.
1) f(u, v) = distance between u, v in a weighted tree.
2) If every nodes have number written, f(u, v) can be median / mode / average/ sum of all numbers in path from u to v.
3) if every nodes have colors assigned f(u, v) can be number of distinct colors between path from u to v.
Any Ideas how to solve these kinds of problems?
One way to solve this kind of problem is to focus on the contribution of each node (edge) in the total sum.
For instance, the first problem we can iterate on edge. For a fixed edge x, we need to calculate the contribution of edge x to the final answer, then the question comes to how many pair of node, whose path passed the certain edge we are fixed now. Then sum all of the contribution by all edges up we will get the answer.
I have done the 1st one before . The idea is that each edge weight gets added for all the paths from the vertices in its subtree and all the vertices not in its subtree . Therefore