×

# 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:

This question is marked "community wiki".

119
accept rate: 0%

19.8k350498541

 0 Could someone explain second solution in more details?Thanks! answered 22 Aug '17, 14:45 1●1 accept rate: 0% Link to the code (22 Aug '17, 23:10)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,768
×1,359
×733
×138
×31
×1

question asked: 20 Aug '17, 20:34

question was seen: 1,073 times

last updated: 22 Aug '17, 23:10