 # TRCNTCT - Editorial

Author: Daniil Melnichenka
Editorialist: Daniil Melnichenka

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:

1. not contain any vertex with index strictly less than X;
2. 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.

### RELATED PROBLEMS:

Could someone explain second solution in more details?Thanks!

//