PROBLEM LINK:
Author: Aleksandar Abas
Tester: Sergey Kulik
Editorialist: Mugurel Ionut Andreica
DIFFICULTY:
MEDIUM
PREREQUISITES:
Trees, Jump Pointers in a Tree
PROBLEM:
Chef has a rooted tree with lengths on edges. For every subtree (rooted at every vertex i) you must find the minimum maximum distance between any two vertices in the subtree.
QUICK EXPLANATION:
We will denote the minimum maximum distance between any two vertices in a subtree by the radius of that subtree. Let the diameter of the subtree be the longest path between any two vertices in the subtree. Then the radius is obtained between one of the endpoints of the diameter and one of the vertices close to the “middle” of the diameter.
Let’s assume that the diameter of the subtree consists of the vertices v(1), …, v(K). Let dist(i,j) be the distance between the vertices i and j in the tree. Let m be the maximum index such that dist(v(1),v(m)) <= dist(v(1),v(K))/2 and dist(v(1),v(m+1)) > dist(v(1),v(K))/2. The middle vertices of the diameter are v(m) and v(m+1), and the radius is min{dist(v(1),v(m+1)),dist(v(m),v(K))}.
We can compute the diameter (and its endpoints) for every subtree rooted at any vertex i in overall O(N) time. In order to find the vertices close to the “middle” of the diameter we can either use the jump pointers technique or we can use an approach similar to the “two pointers” technique. The first option leads to an O(Nxlog(N)) time complexity, while the second option leads to an O(N) time complexity.
EXPLANATION:
We can write a recursive function DFS(x), in which we compute all the needed information:
- diameter(x)=the diameter of the subtree rooted at the vertex x
- dmax(x)=the length of the longest path starting at x and going down in its subtree
- end(x)=a vertex located below x (or equal x) on the longest path starting at x and going down the tree (it may be different depending on whether we use the jump pointers technique or not)
- droot(x)=the distance from the root to the vertex x
- radius(x)=the radius of the subtree rooted at the vertex x (the value that the problem asks us to compute)
DFS(x):
dmax(x) = dmax2 = diameter(x) = radius(x) = 0
end(x) = x
for y child of x:
droot(y) = droot(x) + length of the edge (x,y)
DFS(y)
if diameter(y) > diameter(x):
diameter(x) = diameter(y)
radius(x) = radius(y)
if dmax(y) + length of edge (x,y) > dmax(x):
dmax2 = dmax(x)
dmax(x) = dmax(y) + length of edge (x,y)
end(x) = end(y)
else if dmax(y) + length of edge (x,y) > dmax2:
dmax2 = dmax(y) + length of edge (x,y)
if dmax(x) + dmax2 > diameter(x):
diameter(x) = dmax(x) + dmax2
Let z be the highest ancestor of end(x) such that (dmax2 + droot(z) - droot(x)) > (dmax(x) + dmax2) / 2.
radius(x) = min{dmax2 + droot(z) - droot(x), diameter(x) - (droot(parent(z)) - droot(x)) - dmax2}
In order to compute z we can use the “jump pointers” technique. For every vertex x we compute its ancestor anc(x,j) located 2^j levels higher. Using this table we can start at end(x) and go as far as up the tree as possible, as long as the condition regarding the distances holds. Thus, we can find z in O(log(N)) time.
However, we can do better. We can start at end(x) and repeatedly set end(x)=parent(end(x)) as long as the condition involving distances holds. At the end of these iterations we will have end(x)=z. Although it seems that this approach may take O(N) time for each vertex, we can perform an amortized analysis of the algorithm to prove that it actually takes O(N) time overall.
AUTHOR’S, TESTER’S AND EDITORIALIST’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.