Contribution technique-I
Pre Requisites: trees basic dfs, calculating subtree sizes, basic math
Difficulty: Medium
Today, we will see a good technique in CP known as contribution sums. This technique can be used in many counting problems to make our computations faster.
The basic idea behind this technique is to identify the entities (basic elements) that constitute the final answer. We need an answer to this question: “What is my final answer made up of?” Then, we would iterate on each entity and find its own contribution to the final answer.
Solving a counting problem with the contribution technique might be faster than a normal brute force.
This post will specifically deal with the contribution technique on trees.
Let's start with a simple problem to understand this technique.
Q) Given a tree (with any number of children) of N vertices and N-1 edges rooted at (1). I have to find the sum of the edge lengths between all possible pairs of nodes in the given tree.
Sample example and explanation:
Brute-force:
Consider the above tree with 6 Nodes. There are 15 pairs of nodes that I can choose. I have to find the path length for each pair and add it to my final answer. Let's do a walkthrough on this brute-force approach.
The above image is self-explanatory. Basically, we have tried all possible combinations of choosing two nodes and iterating through its path. In the worst case, each path length can be O(N), and there are O(N²) such pairs of nodes.
So, our brute force solution will have an O(N³) complexity. The above solution may be optimized to O(N²) with some observations but still gives TLE for large N ≤ 10⁵.
Efficient solution: O(N) using contribution technique
Let's see how we can use the idea of contribution here. If we notice carefully that our final answer constitutes only the edges of our tree. (i.e.,) Our final answer is just a collection of edges taken many times. So, our basic entity of the final answer is my edge of the tree.
Let's iterate on each edge and find its contribution. Basically, I am fixing my edge say (u,v), and trying to find how many of the paths contain this (u,v) edge.
See the image below for a better understanding:
Example:
3–4 edge is contained in 5 paths: 4 →3, 4 →1, 4 →2, 4 → 5, 4 → 6.
So, the (3–4) edge contributes a value of 5 to my final answer. Similarly, this can be calculated for other edges too.
Now, a question arises: “How do we efficiently compute occurrences of each edge? ”
Let's do some maths and observations here:
Let's try to find the contribution of (1–3) edge
Any node in the green region paired with any node in the orange region will have (1–3) edge passing by. So, the green region contains three nodes, and my orange region (outside green) also contains three nodes. So 3 x 3 = 9 pairs (u,v) contains this edge passing by.
The green region contains basically subtree_size[u] nodes. My orange region contains (N - subtree_size[u]) nodes.
So the contribution of edge (u, parent[u]) is basically :
So, just summing up the above equation for all “u” gives my answer.
subtreeSize[u] for all nodes can be calculated with a simple dfs on the tree and summing values taking an overall O(N) complexity.
Summary:
Thinking in terms of contributions can lead to a better solution with good time complexity. This technique is more common in competitive coding. We just need to figure out my basic elements and how they affect my final answer. I hope you all have some basic ideas on contributions; for more interesting problems, you can refer to the resource below.
This article is published as a part of the ‘Algo Reads’ under Spider Research and Development Club, NIT Trichy.
Resource:
