CF2002D2 DFS Checker (Hard Version)
Description
This is the hard version of the problem. In this version, you are given a generic tree and the constraints on $ n $ and $ q $ are higher. You can make hacks only if both versions of the problem are solved.
You are given a rooted tree consisting of $ n $ vertices. The vertices are numbered from $ 1 $ to $ n $ , and the root is the vertex $ 1 $ . You are also given a permutation $ p_1, p_2, \ldots, p_n $ of $ [1,2,\ldots,n] $ .
You need to answer $ q $ queries. For each query, you are given two integers $ x $ , $ y $ ; you need to swap $ p_x $ and $ p_y $ and determine if $ p_1, p_2, \ldots, p_n $ is a valid DFS order $ ^\dagger $ of the given tree.
Please note that the swaps are persistent through queries.
$ ^\dagger $ A DFS order is found by calling the following $ \texttt{dfs} $ function on the given tree.
```
``` dfs_order = []
function dfs(v):
append v to the back of dfs_order
pick an arbitrary permutation s of children of v
for child in s:
dfs(child)
dfs(1)
``` ``` Note that the DFS order is not unique.
Input Format
N/A
Output Format
N/A
Explanation/Hint
In the first test case, the permutation $ p_1, p_2, \ldots, p_n $ after each modification is $ [1,3,2],[1,2,3],[3,2,1] $ , respectively. The first two permutations are valid DFS orders; the third is not a DFS order.
In the second test case, the permutation $ p_1, p_2, \ldots, p_n $ after each modification is $ [1,2,5,4,3,6,7],[1,3,5,4,2,6,7],[1,3,7,4,2,6,5],[1,3,7,6,2,4,5] $ , respectively.