$$$f_i$$$ is defined as the $$$\operatorname{mex}$$$ of the prefix subarray of $$$a$$$. According to the definition of $$$\operatorname{mex}$$$, it is obvious that $$$f_i \le f_{i+1}$$$. Therefore, the $$$k$$$-th largest value among $$$f_1, f_2, \ldots, f_n$$$ can be regarded as $$$f_{n-k+1}$$$. Then the original problem is equivalent to swapping two values in the sequence $$$a$$$ at most once so that $$$f_{n-k+1}$$$ is maximized, i.e., maximizing $$$\operatorname{mex}(a_1,a_2,\ldots,a_{n-k+1})$$$.

Let initially $$$v=\operatorname{mex}(a_1,a_2,\ldots,a_{n-k+1})$$$. Then swapping two numbers that are both located in $$$range_1=[1,n-k+1]$$$, or both located in $$$range_2=(n-k+1,n]$$$, will not change the value of $$$v$$$. If the two swapped numbers are respectively in the above two intervals, the optimal solution is obviously to swap the value $$$v$$$ from $$$range_2$$$ to $$$range_1$$$, so that after the swap we can obtain $$$\operatorname{mex}(a_1,a_2,\ldots,a_{n-k+1})=v+1$$$, provided that the number removed from $$$range_1$$$ is greater than $$$v$$$.

By the definition of $$$\operatorname{mex}$$$, $$$v$$$ is the minimum value in $$$range_2$$$. Then a simple method is to choose the maximum value $$$x$$$ from $$$range_1$$$ and the minimum value $$$y$$$ from $$$range_2$$$. If $$$x \gt y$$$, swap the two; if $$$x \lt y$$$, it means $$$range_1$$$ contains all numbers from $$$0$$$ to $$$v-1$$$, so not swapping is the optimal solution.

Time complexity: $$$O(n)$$$

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];

        if (k == 1) {
            cout << -1 << '\n';
        } else {
            auto x = max_element(a.begin(), a.begin() + n - k + 1) - a.begin();
            auto y = min_element(a.begin() + n - k + 1, a.end()) - a.begin();
            if (a[x] > a[y]) {
                cout << x + 1 << ' ' << y + 1 << '\n';
            } else {
                cout << -1 << '\n';
            }
        }
    }
    return 0;
}

• Heat
• Mid
• Horrendous
• Didn't Solve

First, let us consider several simplest cases with only two frogs:

1. If the cells containing the two frogs share an edge, i.e., they are adjacent horizontally or vertically, then they can jump to each other's positions respectively, thereby keeping the total number of frogs in each row and each column required by the problem unchanged.

2. If the cells containing the two frogs share a cell vertex, i.e., they are diagonally adjacent, then the frog on the left can jump to the right, and the frog on the right can jump to the left, thereby keeping the total number of frogs in each row and each column required by the problem unchanged.

Since every column in the given grid contains at least one frog, if the total number of frogs in the input is even, we can always select, from left to right, two frogs satisfying one of the above two cases, and make them jump according to the above method, thereby satisfying the requirements of the problem.

If the total number of frogs in the input is odd, there is no valid solution that keeps the total number of frogs in each row and each column required by the problem unchanged. We assume that there is a valid solution. Since jumping left and right does not affect the total number of frogs in each row, the number of frogs jumping down and the number of frogs jumping up are obviously equal, and after these frogs jump they do not affect the total number of frogs in each column, and these frogs are even in number. Since the total number of frogs is odd, if we keep only the frogs that jump left and right in this solution, the total number of these frogs is odd, and the solution should still be valid. Since the total number of rows no longer matters, we can imagine that the grid becomes a single row, and each cell contains 1 or 2 frogs. Then consider all frogs at the leftmost side; they can only jump to the right, so the cell immediately to the right of this cell must contain an equal number of frogs jumping to the left, in order to keep the total number of frogs in each column unchanged. Since the total number of frogs is odd, one frog will remain in the end, and after jumping it will break the requirements of the problem.

Therefore, we obtain the final conclusion: when the total number of frogs is even, there is always a solution; when the total number is odd, it suffices to remove one frog so that the total number becomes even.

#include <bits/stdc++.h>
using namespace std;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string s1, s2;
        cin >> s1 >> s2;
        auto tot = ranges::count(s1, 'f') + ranges::count(s2, 'f');
        cout << tot % 2 << '\n';
    }
    return 0;
}

• Heat
• Mid
• Horrendous
• Didn't Solve

Fix $$$k$$$. Operations only add black cells and each blacks exactly two cells at distance in $$$[1,k]$$$, so a final black set $$$B$$$ is achievable iff $$$B \supseteq a$$$, $$$|B| \le n+x$$$, and in the sorted order of $$$B$$$ every cell has a neighbor in $$$B$$$ at distance at most $$$k$$$: one operation per cell together with its partner paints exactly $$$B$$$. Adding cells only shrinks gaps, so extras never hurt.

Call $$$a_i$$$ bad if all its adjacent gaps in $$$a$$$ exceed $$$k$$$ (for the endpoints, the single gap). Non-bad cells already have a partner inside $$$a$$$; each bad cell needs one from the added set $$$S = B \setminus a$$$. One added cell $$$p$$$ serves at most two bad cells: if it served bad cells $$$a_i \lt a_j$$$ with $$$j \ge i+2$$$, the disjoint gaps $$$a_{i+1}-a_i$$$ and $$$a_j-a_{j-1}$$$, both exceeding $$$k$$$, lie inside $$$[a_i,a_j]$$$ and force $$$a_j-a_i \gt 2k$$$, contradicting $$$|p-a_i|,|p-a_j| \le k$$$. So only consecutive bad cells with $$$a_{i+1}-a_i \le 2k$$$ may share $$$p$$$, and both cases are realizable: $$$p=a_i+k$$$ lies strictly between two consecutive bad cells (hence $$$p \notin a$$$) and is within $$$k$$$ of both; $$$p=a_i+1$$$ serves a lone bad cell, and $$$p \notin a$$$ since every adjacent gap of a bad cell exceeds $$$k \ge 1$$$.

Hence the minimum $$$|S|$$$ equals the number of bad cells minus the maximum number of disjoint consecutive bad pairs with gap at most $$$2k$$$; this is a matching on a path, so the left-to-right greedy that pairs whenever possible is optimal, which is exactly what the check function computes. Thus $$$k$$$ is feasible iff this greedy count does not exceed $$$x$$$.

Feasibility is monotone in $$$k$$$, since all conditions above only relax as $$$k$$$ grows, and $$$k=10^9$$$ always works because then no cell is bad. Binary searching the minimum feasible $$$k$$$ on $$$[1,10^9]$$$ with an $$$O(n)$$$ check costs $$$O(n \log 10^9)$$$ per test case, well within the limits.

Time complexity: $$$O(n\log V)$$$

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MAXN 200005

int n,x,lef[MAXN],a[MAXN];

inline bool check( int d ){
	int c = 0;
	for( int i = 1 ; i <= n ; i ++ ) lef[i] = 0;
	for( int i = 1 ; i <= n ; i ++ ){
		int L = i == 1 || a[i] - a[i - 1] > d;
		int R = i == n || a[i + 1] - a[i] > d;
		lef[i] = L && R;
	}
	for( int i = 1 ; i <= n ; i ++ ){
		if( lef[i] ){
			if( i < n && lef[i + 1] ){
				if( a[i + 1] - a[i] <= 2 * d ) lef[i] = lef[i + 1] = 0,c ++;
				else lef[i] = 0,c ++;
			}
			else{
				lef[i] = 0,c ++;
			}
		}
	}
	return c <= x;
}

inline void solve(){
	scanf("%d%d",&n,&x);
	for( int i = 1 ; i <= n ; i ++ ) scanf("%d",&a[i]);
	int l = 1,r = (ll)1e9,ans = -1;
	while( l <= r ){
		int mid = ( l + r ) >> 1;
		if( check( mid ) ) ans = mid,r = mid - 1;
		else l = mid + 1;
	}
	printf("%d\n",ans);
}

signed main(){
	int t; scanf("%d",&t);
	while( t -- ) solve();
	return 0;
}

• Heat
• Mid
• Horrendous
• Didn't Solve

First, if the original graph has no edges, then choosing a center vertex and adding an edge from every other vertex to this center is clearly an optimal solution, yielding a maximum independent set of size $$$n−1$$$.

If the original graph does contain edges, then for a tree that is a connected component with at least one edge, take a vertex $$$u$$$ adjacent to some leaf. This vertex $$$u$$$ is necessarily not in some maximum independent set. For every other connected component of the original graph, arbitrarily choose one vertex and connect it to $$$u$$$. This yields an independent set whose size is the same as the maximum independent set of the original graph. Since the maximum independent set size of the resulting tree cannot exceed that of the original graph before adding edges, the tree constructed in this way is one of the optimal solutions.

Time Complexity: $$$O(n)$$$.

#include<bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int k;
        cin >> k;
        vector<vector<vector<int>>> trees(k);
        for (int i = 0; i < k; i++) {
            int n;
            cin >> n;
            trees[i].assign(n, {});
            for (int j = 0; j < n - 1; j++) {
                int x, y;
                cin >> x >> y;
                x--, y--;
                trees[i][x].push_back(y);
                trees[i][y].push_back(x);
            }
        }

        int ri = -1, rj = -1;
        for (int i = 0; i < k && ri == -1; i++) {
            if (trees[i].size() > 1) {
                for (int j = 0; j < trees[i].size() && ri == -1; j++) {
                    if (trees[i][j].size() == 1) {
                        ri = i, rj = trees[i][j][0];
                    }
                }
            }
        }
        if (ri == -1) ri = rj = 0;
        for (int i = 0; i < k; i++) {
            if (i == ri) continue;
            cout << i + 1 << " 1 " << ri + 1 << " " << rj + 1 << "\n";
        }
    }
    return 0;
}

• Heat
• Mid
• Horrendous
• Didn't Solve

Consider a single R in $$$s$$$ at position $$$i$$$. There are two cases.

Case 1: there is a W in front of this R. Let $$$j$$$ be the index of the nearest such W. It is not hard to see that, by inserting $$$t$$$, we can make the answer take every value in $$$[j, j+m]$$$, where $$$m = |t|$$$. Clearly the answer can never be smaller than $$$i$$$, but it can be larger. Now look at the last occurrence of W in $$$t$$$ (say it is the $$$k$$$-th W of $$$t$$$): we may read it last, and then the answer can also reach $$$i-1+k$$$. This part is contiguous as well, so the set of attainable answers is exactly the interval $$$[j, \max(j+m, i-1+k)]$$$.

Case 2: there is no W in front of this R. Then $$$0$$$ is attainable, and we can compute the answer directly. Take a W of $$$t$$$ at position $$$j$$$; it lets $$$[j, j+i-1]$$$ be absorbed into the answer interval. Hence the answer is the size of the union of all intervals $$$[j, j+i-1]$$$.

To get the answer for every R, iterate over $$$i$$$ from left to right; then all these intervals grow simultaneously. We maintain the number of currently alive intervals, and for each of them the moment at which it catches up with the next interval; at those moments we subtract its contribution and retire it.

Complexity: $$$O(n+m)$$$.

#include<bits/stdc++.h>
using namespace std;

#define MAXN 400005

int len[2],f[2],g[2],difs[MAXN];
char s[2][MAXN],t[MAXN];

inline void Getans( int id ){
	int g = 0,cnt = 0;
	for( int i = 1 ; i <= len[id ^ 1] ; i ++ ) if( s[id ^ 1][i] == 'W' ) g = i,cnt ++;
	vector<int> A,dif;
	for( int i = 1 ; i <= len[id ^ 1] ; i ++ ) if( s[id ^ 1][i] == 'W' ) A.emplace_back( i );
	for( int i = 0 ; i + 1 < (int)A.size() ; i ++ ) difs[A[i + 1] - A[i] - 1] ++;
	if( g ) difs[len[0] + len[1]] ++;
	for( int i = len[0] + len[1] - 1 ; i >= 0 ; i -- ) difs[i] += difs[i + 1];
	for( int i = 1 , c = 0 ; i <= len[id] ; i ++ ){
		if( s[id][i] == 'R' ){
			if( !c ){
				printf("%d ",cnt + 1);
				cnt += difs[i];
			}
			else{
				int L = c;
				int R = max( c + len[id ^ 1] , g ? i - 1 + g : 0 );
				printf("%d ",R - L + 1);
			}
		}
		else c = i;
	}
	for( int i = 0 ; i <= len[0] + len[1] ; i ++ ) difs[i] = 0;
	puts("");
}

inline void solve(){
	scanf("%d%d%s%s",&len[0],&len[1],s[0] + 1,s[1] + 1);
	Getans( 0 ),Getans( 1 );
}

signed main(){
	int t; scanf("%d",&t);
	while( t -- ) solve();
	return 0;
}

• Heat
• Mid
• Horrendous
• Didn't Solve

If we choose a child of the current root as the new root, do the vertices outside that child's subtree still matter?

We can consider that, on the next move, we simply delete all vertices that were outside that subtree. The only difference is that this effectively adds one extra operation: passing one turn.

This suggests a tree DP solution. However, we certainly cannot run a separate tree DP for every possible choice of root. So what should we do?

Use rerooting DP.

We define two states:

\begin{itemize} \item $$$f(u,p)$$$: The current root is $$$u$$$, and this state is obtained by re-rooting from $$$p$$$ to $$$u$$$. Therefore, the current player still has one extra Pass available. $$$f(u,p)=1$$$ means the current player wins, and $$$f(u,p)=0$$$ means the current player loses.

\item $$$g(u)$$$: The current root is $$$u$$$, and there is no extra Pass available. $$$g(u)=1$$$ means the current player wins, and $$$g(u)=0$$$ means the current player loses. \end{itemize}

If Bob chooses vertex $$$r$$$ as the initial root, then Alice starts from state $$$g(r)$$$.

To compute all values efficiently, we use rerooting DP.

First, choose an arbitrary vertex, say $$$1$$$, as a temporary root.

Define

Also define

Finally, define

that is, the number of children $$$v$$$ of $$$u$$$ such that $$$\mathrm{down}[v]=0$$$.

Now we derive the transitions.

\textbf{Computing down[u]}

For $$$\mathrm{down}[u]$$$, suppose $$$u$$$ has $$$c$$$ children in the temporary rooted tree.

In the state $$$f(u,\mathrm{parent}(u))$$$, the current player has one extra Pass. There are two possibilities:

\begin{itemize} \item If there exists a child $$$v$$$ such that $$$\mathrm{down}[v]=0$$$, then the current player can immediately move the root to $$$v$$$, leaving a losing state to the opponent.

\item Otherwise, all children satisfy $$$\mathrm{down}[v]=1$$$. In that case, the only effect of future moves is to remove available directions one by one together with the one extra Pass. For an $$$f$$$-state, this means the current player wins if and only if the number of available child directions is even. \end{itemize}

So

In particular, if $$$u$$$ is a leaf, then $$$c=0$$$, so $$$\mathrm{down}[u]=1$$$.

\textbf{Computing up[v]}

Next, consider a child $$$v$$$ of $$$u$$$. We want to compute

This is the state where the current root is $$$u$$$, the extra Pass is available, and the direction toward $$$v$$$ is excluded.

The value $$$\mathrm{up}[v]$$$ is $$$0$$$ if and only if all of the following conditions hold:

\begin{enumerate} \item The parent side does not provide a losing direction, that is,

\item After excluding $$$v$$$, none of the remaining children provides a losing direction, that is,

\item The parity of the remaining available directions is losing for an $$$f$$$-state. After excluding $$$v$$$, the number of available directions is $$$\deg(u)-1$$$, so we need

\end{enumerate}

Therefore,

\textbf{Computing g(u)}

Finally, we compute $$$g(u)$$$.

If $$$u$$$ is chosen as the initial root, then the current player has no extra Pass, and all neighbors of $$$u$$$ are available directions.

The value $$$g(u)$$$ is $$$1$$$ in the following cases:

\begin{itemize} \item There exists a child $$$v$$$ such that $$$\mathrm{down}[v]=0$$$.

\item The vertex $$$u$$$ has a parent and $$$\mathrm{up}[u]=0$$$.

\item All available directions lead to winning $$$f$$$-states, and $$$\deg(u)$$$ is odd. \end{itemize}

So

\textbf{Algorithm}

The algorithm is now clear:

\begin{enumerate} \item Run one DFS from the temporary root to compute all $$$\mathrm{down}[u]$$$ and $$$h(u)$$$.

\item Run a second DFS to compute all $$$\mathrm{up}[u]$$$, and at the same time evaluate all $$$g(u)$$$.

\item If there exists a vertex $$$r$$$ such that $$$g(r)=0$$$, then Bob can choose $$$r$$$ as the initial root and win.

\item Otherwise, Alice wins no matter which root Bob chooses. \end{enumerate}

The total time complexity is $$$O(n)$$$, and the memory complexity is also $$$O(n)$$$.

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int n;
    cin >> n;

    vector<vector<int>> e(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    vector<int> fa(n + 1), order;
    order.reserve(n);

    fa[1] = 0;
    order.push_back(1);

    for (int i = 0; i < (int)order.size(); i++) {
        int u = order[i];
        for (int v : e[u]) {
            if (v == fa[u]) continue;
            fa[v] = u;
            order.push_back(v);
        }
    }

    vector<int> down(n + 1), up(n + 1);

    for (int i = n - 1; i >= 1; i--) {
        int u = order[i];

        int lose = 0;
        for (int v : e[u]) {
            if (fa[v] == u && down[v] == 0)
                lose++;
        }

        int child_cnt = (int)e[u].size() - 1;

        down[u] = (lose > 0 || child_cnt % 2 == 0);
    }

    vector<int> lose_cnt(n + 1);

    for (int u : order) {
        int cnt = 0;

        if (fa[u] && up[u] == 0)
            cnt++;

        for (int v : e[u]) {
            if (fa[v] == u && down[v] == 0)
                cnt++;
        }

        lose_cnt[u] = cnt;

        for (int v : e[u]) {
            if (fa[v] != u) continue;

            int cur = cnt - (down[v] == 0);

            up[v] = (cur > 0 || ((int)e[u].size() - 1) % 2 == 0);
        }
    }

    vector<int> ans;

    for (int u = 1; u <= n; u++) {
        bool win = (lose_cnt[u] > 0 || (int)e[u].size() % 2 == 1);

        if (!win)
            ans.push_back(u);
    }

    if (ans.empty()) {
        cout << "Alice\n";
        return;
    }

    cout << "Bob\n";
    cout << ans.size() << '\n';

    for (int i = 0; i < (int)ans.size(); i++) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--)
        solve();

    return 0;
}

• Heat
• Mid
• Horrendous
• Didn't Solve

Represent an interval $$$[l,r]$$$ by a directed edge

If we know the reports for $$$[l,k]$$$ and $$$[k+1,r]$$$, then we have

so combining reports is exactly concatenating directed paths. Therefore, after making some direct queries, the report for $$$[l,r]$$$ can be obtained iff there is a directed path from $$$l$$$ to $$$r+1$$$.

Now consider the graph formed by the required intervals, but ignore edge directions: for every required $$$[l,r]$$$, add an undirected edge

Suppose one connected component contains $$$s$$$ distinct vertices. We claim that its contribution to the answer is exactly

First, at least $$$s-1$$$ queries are necessary. For every required edge, its two endpoints must be connected by the queried intervals, so all vertices of this component must belong to the same connected component after ignoring directions. Connecting $$$s$$$ vertices requires at least $$$s-1$$$ edges.

Using additional vertices or connecting several required components together cannot improve this bound: if a connected component of queried edges contains $$$s$$$ relevant vertices coming from $$$k$$$ required components, then it contains at least $$$s-1$$$ queried edges, while those required components contribute only $$$s-k \le s-1$$$.

The bound is also achievable. Sort all vertices of one component:

Query

These queries form the directed path

For every required interval $$$[l,r]$$$, both $$$l$$$ and $$$r+1$$$ are vertices of this component and $$$l \lt r+1$$$, so the path contains a directed subpath from $$$l$$$ to $$$r+1$$$. Hence its report can be obtained.

Therefore, for every configuration,

This is exactly the number of successful merges when inserting all edges $$$(l,r+1)$$$ into a DSU.

The only remaining difficulty is that every modification deletes one old edge and inserts a new one. We process all modifications offline. Each version of an interval is active on one continuous range of times, so we add these active ranges to a segment tree over time and traverse it with a rollback DSU.

At every leaf, the DSU contains exactly the edges present in that configuration. Thus the number of successful unions is the required answer.

No path compression should be used in the rollback DSU; union by size is sufficient.

Let $$$V$$$ be the number of different values among all $$$l$$$ and $$$r+1$$$. We may coordinate-compress them, so $$$V=O(m+q)$$$. There are $$$O(m+q)$$$ different interval versions, and each is stored in $$$O(\log(q+1))$$$ segment-tree nodes.

The total complexity is

time and

memory.

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
const int mod = 998244353;
const int INF = 1e18;
const int N = 5e5 + 5;

struct DSU {
    vi fa;
    vector<array<int, 4>> stk;

    DSU(int n) : fa(n, -1) {}

    int find(int x) {
        while (fa[x] >= 0)
            x = fa[x];
        return x;
    }

    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y)
            return;
        if (-fa[x] < -fa[y])
            swap(x, y);
        stk.pb({x, y, fa[x], fa[y]});
        fa[x] += fa[y];
        fa[y] = x;
    }

    int snap() {
        return (int)sz(stk);
    }

    void rollback(int p) {
        while ((int)sz(stk) > p) {
            auto [x, y, fx, fy] = stk.back();
            stk.pop_back();
            fa[x] = fx;
            fa[y] = fy;
        }
    }

    int rank() {
        return (int)sz(stk);
    }
};

struct qy {
    int l, r;
    pii e;
};

void init() {}

void solve() {
    int n, m, q;
    cin >> n >> m >> q;

    vpii cur(m);
    for (auto &[l, r] : cur) {
        cin >> l >> r;
        ++r;
    }

    vector<tiii> upd(q);
    for (auto &[p, l, r] : upd) {
        cin >> p >> l >> r;
        --p, ++r;
    }

    vi st(m, 0);
    vector<qy> evt;
    evt.reserve(m + q);

    for (int t = 1; t <= q; t++) {
        auto [p, l, r] = upd[t - 1];
        evt.pb({st[p], t, cur[p]});
        cur[p] = {l, r};
        st[p] = t;
    }
    for (int i = 0; i < m; i++)
        evt.pb({st[i], q + 1, cur[i]});

    int tot = q + 1, base = 1;
    while (base < tot)
        base <<= 1;
    vvpii seg(base << 1);

    auto add = [&](int l, int r, pii e) {
        for (l += base, r += base; l < r; l >>= 1, r >>= 1) {
            if (l & 1)
                seg[l++].pb(e);
            if (r & 1)
                seg[--r].pb(e);
        }
    };

    for (auto [l, r, e] : evt)
        add(l, r, e);

    DSU dsu(n + 2);
    vi ans(tot);

    auto dfs = [&](auto &&self, int u) -> void {
        int p = dsu.snap();
        for (auto [x, y] : seg[u])
            dsu.merge(x, y);

        if (u >= base) {
            int t = u - base;
            if (t < tot)
                ans[t] = dsu.rank();
        } else {
            self(self, u << 1);
            self(self, u << 1 | 1);
        }
        dsu.rollback(p);
    };

    dfs(dfs, 1);
    for (int x : ans)
        cout << x << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

• Heat
• Mid
• Horrendous
• Didn't Solve