PROBLEM LINK:Author: 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 divideandconq. 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:
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$. 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 prefixminimum (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$. 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 divideandconquer 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 divideandconquer 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 $RL$. 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. RELATED PROBLEMS:
This question is marked "community wiki".
asked 20 Aug '17, 20:34
