PROBLEM LINK:Author: Zain Ali DIFFICULTY:MEDIUM PREREQUISITES:DSU (Disjoint Set Union) PROBLEM:You are given a tree on vertices $1,2,\ldots,N$. Initially, each vertex contains no bank branch, though they appear in vertices over the time. You need to process two types of queries:
QUICK EXPLANATION:Process the queries offline in reverse order. Get rid of multiple bank branches opening in a vertex by only considering the first event. In reverse order, the second query is the same, while the first query means some bank branch is closing in the vertex. Maintain disjoint sets of vertices that are obtained as connected components after removal of all vertices with bank branches. The answer to the second type query for each vertex in such component is the same. For each component, maintain two indices of nodes that are maximum and second maximum in the set $V$. The first type queries in reverse order result in merges of the components. Maintain the size of the components to merge smaller component to larger; the indices of the two nodes may only decrease, and decrementing them naively for the larger component (checking whether the decremented index lies in another component) results in an $O(N\log N)$ time complexity. EXPLANATION:Refer to the "Quick explanation" section for the outline of the solution and the first step: reversing the queries and getting rid of the redundant ones. Maintain disjoint sets of vertices $S_i$ that have no bank branches and that are connected if we disallow entering the vertices with bank branches: that is, sets $S_i$ at each moment can be obtained as connected components that appear after the removal of all vertices with bank branches. Why do we need these sets? The reason is that for the vertices of the same set the answer to the second query is the same. We will call these sets 'components'. Store the components $S_i$ in a DSU data structure. In addition, for each component, store the indices of the two nodes, $m_1$ and $m_2$ that are the maximum ($m_1$) and the second maximum ($m_2$) vertices in the set $V$ for this component, so that the $m_2$ is the answer to the second type query for all vertices of the component. Also, for each component, maintain its size, and in the implementation of the $Unite$ operation of DSU make smaller component children of larger component's root. Suppose that we know how to update the structure when the bank branches are closing. Then, the answer to the second type query can be easily obtained: if there is a bank branch the vertex, it is $N2$, otherwise, it is $m_2$ of the corresponding component. Suppose we now have a first type query to close the bank branch at vertex $C$. First, create vertex $C$ as a separate component. Traverse all edges incident to $C$ and if they lead to a vertex of without the bank branch, make a DSU merge operation of the corresponding components. How do the indices $m_1$ and $m_2$ change when two components are being merged? First, notice that $m_1$ and $m_2$ for the components other than the two being merged remain intact: for the vertex to belong to the set $V$ of the component $S$ it is necessary and sufficient for it either to have a bank branch or to belong to the component other than $S$. Thus, the merge of the components different from $S_i$ does not affect it's set $V$ and thus does not affect it's $m_1$ and $m_2$ indices. Suppose we merge the components $S_1$ and $S_2$, $S_1\geS_2$. Then the following "naive" algorithm turns out to be fast enough to recompute the indices:
It is easy to see that the algorithm is correct (the indices may only decrease, and we check all candidates decrementing by one). What is it's time complexity? The key observation is that for the component $S$ of size $S$ the total number of operations required to decrement its indices in all merge events may not exceed $O(S)$, provided that this component was the largest in all merges, that is, we used its indices $m_1$ and $m_2$ as the reference point. Indeed, when decrementing, we stop as soon as the current index does not lie in $S$. Thus, the number of times we continue iteration may not exceed $S$, or $2S$ when two indices are taken into account. Now consider each component at the moment it gets merged into the larger component  we can bound the number of decrements for it as $O(S_i)$. The total number of decrements thus does not exceed ($C$ is the constant used in BigO notation): $$C\times \sum_{\text{over all merges of the components}} \text{smallest component in the merge}=O(N\log N)$$ The asymptotical equality is from the fact that each vertex may only move from the smaller component to the larger component $O(\log N)$ times, as each move double the size of the component the vertex belongs to. The overall time complexity is $O(N\log N+Q)$ (we assume the DSU operation time complexity $O(1)$), the memory complexity is $O(N+Q)$. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. Tester's solution can be found here. RELATED PROBLEMS:asked 14 Nov '17, 01:25

My Solution is different : C++ Code
answered 14 Nov '17, 21:01

In case someone else has problem understanding this editorial like I did:
Also from what I understand in complexity analysis, it assumes that to merge $S_1$ and $S_2$ it takes $O(S_2)$ time. Which would require us to store $V_{S_i}$. But I did not store $V_{S_i}$ and the solution still passed so ¯\_(ツ)_/¯. My solution. It should be way easier to follow than the Author's and Tester's solution. answered 19 Nov '17, 03:16

@nilesh3105 could you please explain the cal function in your code? answered 22 Nov '17, 02:27

@nilesh3105 Amazingly well written solution, but there's a corner case, where your solution will fail. This one: 1 1 2 1 1 2 1 But anyways, thanks a lot, your solution helped me understand the problem very well :). answered 31 Jul, 12:48

I think there is a typo in 4th Paragraph of Explanation section. "it is N1, otherwise" seems to be correct. I guess editorialist is assuming 0based indexing.