This is the hard version of the problem. The difference between the versions is that in this version, the constraints on (t) and (n) are larger. You can hack only if you solved all versions of this problem. Maple is given a rooted tree consisting of (n) vertices numbered from (1) to (n), where the root has index (1). Each vertex of the tree is labeled either zero or one. Unfortunately, Maple forgot how the vertices are labeled and only remembers that there are exactly (k) zeros and (n - k) ones. For each vertex, we define the name of the vertex as the binary string formed by concatenating the labels of the vertices from the root to the vertex. More formally, (\text{name}_1 = \text{label}_1) and (\text{name}_u = \text{name}_{p_u} + \text{label}_u) for all (2\le u\le n), where (p_u) is the parent of vertex (u) and (+) represents string concatenation. The beauty of the tree is equal to the length of the longest common subsequence(^{\text{∗}}) of the names of all the leaves (^{\text{†}}). Your task is to determine the maximum beauty among all labelings of the tree with exactly (k) zeros and (n - k) ones. (^{\text{∗}})A sequence (a) is a subsequence of a sequence (b) if (a) can be obtained from (b) by the deletion of several (possibly, zero or all) element from arbitrary positions. The longest common subsequence of strings (s_1, s_2, \ldots s_m) is the longest string that is a subsequence of all of (s_1, s_2, \ldots, s_m). (^{\text{†}})A leaf is any vertex without children. Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 10^4)). The description of the test cases follows. The first line of each test case contains two integers (n) and (k) ((2 \leq n \leq 2\cdot 10 ^ 5), (0 \leq k \leq n)) — the number of vertices and the number of vertices labelled with zero, respectively. The se