PROBLEM LINK:
Author: Daniil Melnichenka
Tester: Hasan Jaddouh
Editorialist: Daniil Melnichenka
DIFFICULTY:
Hard
PREREQUISITES:
Dfs, divide and conquer or segment tree.
PROBLEM:
Given a tree of N vertices, find a number of intervals [L, R], such that if we leave only vertices from this interval in the tree, the resulting graph would be connected.
QUICK EXPLANATION:
Solve the task for a fixed root and apply divide-and-conq.
EXPLANATION:
Let’s count the number of intervals [L, R] that contain vertex N/2. We can color vertices which indices are less than N/2 in blue, others in red.
How can we check if a pair (X, Y), where X is blue and Y is red, is a valid pair? Let’s consider all the blue vertices V (such that V \ge X). Paths from V to N/2 should:
- not contain any vertex with index strictly less than X;
- not contain any vertex with index strictly more than Y. Some symmetrical conditions should be hold for vertex Y.
Let’s take a blue vertex X. We need to know:
low_X = the minimal index among the vertices containing in all paths from vertices V (X \le V \le N/2 ) to vertex N/2.
high_X = the maximal index among the vertices containing in all paths from vertices V (X \le V \le N/2 ) to vertex N/2.
We can firstly calculate low_x = the minimal index on path from X to N/2 (and similar values for high_X) and then make some technique like prefix-minimum (thus low_X = min( low_X, low_{X+1} )).
Similarly for every red vertex we need to calculate:
low_Y = the minimal index among the vertices containing in all paths from vertices V (N/2 \le V \le Y) to vertex N/2.
high_Y = the maximal index among the vertices containing in all paths from vertices V (N/2 \le V \le Y) to vertex N/2.
Obviously a blue vertex X is a candidate if low_X = X, a red vertex Y is a candidate if high_Y = Y. A pair (X, Y), where both X and Y are candidates, is valid if high_X \le Y and low_Y \ge X. We can note that as X decreases, high_X increases; and as Y increases, low_X decreases. Evidently we can loop vertex X from N/2 to 1 and use a two pointer technique to count an interval of red vertices that are valid for current X.
The entire algorithm described above works in O(N). Now let’s use a divide-and-conquer technique to get O(NlogN) and solve the whole task. Let’s call the vertex \frac{L + R}{2} a root of the interval [L,R]. In every layer of divide-and-conquer we should run dfs from all the roots of this layer. But it will be O(N^2) now. Consequently in dfs for some interval [L,R] we should never visit vertices that don’t belong interval [L,R]. If some vertex V from the interval [L,R] can’t be reached from vertex \frac{L + R}{2} in this way then we should assign low_V=-infinity and high_V = infinity. Thus it is O(N) for each layer and the entire complexity is O(NlogN).
ALTERNATIVE SOLUTIONS:
Let’s fact that the range [L, R] is valid if the number of edges that connect vertices from that range is R-L. So, we iterate L and maintain in segment tree the number of missing edges for each R in segment tree. So this value would be zero, if R is valid for our L. The number of zeroes can be calculated with segment tree that knows the number of maximums on range. The complexity is also O(NlogN).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.