PROBLEM LINK
CONTEST PANEL
Author: Ildar Gainullin
Tester: Oleksandr Kulkov
Editorialist: Prateek Gupta
PREREQUISITES
Binary Lifting on a tree, lowest common ancestor, depth first search.
DIFFICULTY
EASY MEDIUM
PROBLEM
Given a tree with each node having some value. You need to find the cost of path from each node v to the root of the tree. Cost of each node u in path is the minimum of value of each node lying below u and is in path from (u,\ v).
EXPLANATION
The problem involves using the concept of dynamic programming over a tree while moving from root to the bottom of the tree. Let DP(x) denote the cost of path while moving from vertex x to the root of the tree i.e 1. While we arrive at node x, we have already calculated the DP values for all nodes in path from 1 to Parent[x]. Now, for calculating the answer for node x, we need to find the greatest ancestor y of x in path from 1 to Parent[x], where all the nodes in path from x to y have their values greater than or equal to the given value of the node x.
If A[x] denotes the node value of x and cnt[x] denotes the number of nodes in path from 1 to x, then the following equation holds true.
The only thing remaining is for each node x to calculate the greatest ancestor where all the nodes from node x to the ancestor have value greater than or equal to A[x]. One of the approaches is to pre-process this while calculating LCA and then apply binary lifting.
We define up[x][i] as the node that is ancestor of x at (2^i)-th distance from x.
Then, val[x][i] can be said as the minimum value of all the nodes from x to up[x][i].
set(up, -1)
up[x][0] = Parent[x]
for ( int i = 1 to 19 ) {
if ( up[x][i - 1] != -1 ) {
up[x][i] = up[up[x][i - 1]][i - 1]
}
}
val[x][0] = min(A[x], A[Parent[x]]
for ( i = 1 to 19 ) {
if ( up[x][i] != -1 ) {
val[x][i] = min(val[x][i - 1], val[up[x][i - 1]][i - 1])
}
}
Now, that we have preprocessed everything, how do we calculate the greatest ancestor of x such that minimum of values of nodes from x to this greatest ancestor in the path has value >= A[x]. This can be computed by binary lifting. For more details on binary lifting, check here. Anyways, let’s proceed to look at the pseudo code.
int vertex = x;
for ( i = 19 to i = 0 ) {
if ( up[vertex][i] != -1 ) {
if ( val[vertex][i] >= A[x] ) {
vertex = up[vertex][i];
}
}
}
Now, up[vertex][0] will be the node having value < A[x]. Hence, all nodes from vertex to x will be affected by A[x] and will use this value as their cost. You might want to look at the above DP equation written which might make a little more sense to you now.
For details on the implementation, have a look at the author or tester’s solution.
SOLUTIONS
Author solution can be found here.
Tester solution can be found here.
