• Amazing
• Good
• Average
• Bad

• Very Hard
• Hard
• Average
• Easy
• Very Easy

• A
• B
• C
• D
• E
• F
• G1
• G2

• A
• B
• C
• D
• E
• F
• G1
• G2

Every character of $$$a$$$ is flipped in exactly one string. Therefore, if $$$a_i = 1$$$, we need to add $$$n-1$$$ to the answer (since the $$$i$$$-$$$th$$$ character will stay $$$1$$$ for $$$n-1$$$ strings), and if $$$a_i = 0$$$ we need to add $$$1$$$ (since the $$$i$$$-$$$th$$$ character will be $$$1$$$ in exactly one string).

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n; cin >> n;
    string s; cin >> s;
    int ans = 0;
    for (auto x: s) {
        if (x == '0') ans++;
        else ans += n - 1;
    }
    cout << ans << '\n';
}
 
int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Amazing
• Good
• Average
• Bad
• Didn't Solve

If $$$x = n$$$ then we can output any permutation, since in order for the $$$\operatorname{MEX}$$$ to be equal to $$$n$$$, every value $$$0, 1, ..., n-1$$$ must appear. Otherwise, we want to build a permutation $$$p$$$ such that two main conditions hold.

Firstly, we want $$$x$$$ to appear on the final strip as soon as possible. In other words, the first index $$$i$$$ such that $$$\operatorname{MEX}(p_1, p_2, ..., p_i) = x$$$ must be minimized. In addition, the index $$$j$$$ such that $$$p_j = x$$$ must be maximized, since the $$$\operatorname{MEX}$$$ of a set that contains $$$x$$$ cannot be equal to $$$x$$$.

There are a lot of constructions that satisfy those conditions. One of them is the permutation $$$p = [0, 1, ..., x-1, x+1, ..., n-1, x]$$$.

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n, x; cin >> n >> x;
    for (int i = 0; i < x; i++) cout << i << " ";
    for (int i = x+1; i < n; i++) cout << i << " ";
    if (x < n) cout << x;
    cout << '\n';
}
 
int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Amazing
• Good
• Average
• Bad
• Didn't Solve

Suppose that the two arrays $$$a$$$ and $$$b$$$ of size $$$n$$$ are called $$$s$$$-complementary if and only if $$$a_i + b_i = s$$$ for all $$$1 \le i \le n$$$.

Observation 1: If we know every element of $$$a$$$, and we know $$$s$$$, we can uniquely determine the elements of $$$b$$$.

We split the problem into two cases.

The first case is if there exists at least one element in $$$b$$$ that is not missing. Then we know the required sum $$$s = a_i + b_i$$$ for every $$$1 \le i \le n$$$. For every index $$$i$$$, we know $$$b_i = s - a_i$$$. If $$$0 \le s - a_i \le k$$$ doesn't hold for some index, the answer is $$$0$$$, since it is impossible for the two arrays to be complementary while $$$0 \le b_i \le k$$$. Otherwise, the answer is $$$1$$$ from Observation 1.

The second case is if every element of $$$b$$$ is missing:

Observation 2: if $$$a$$$ and $$$b$$$ are $$$s$$$-complementary, then the maximum element of $$$b$$$ is positioned at the index where the minimum element of $$$a$$$ is positioned at. That is because in order for $$$a_i + b_i = s$$$ to hold when $$$a_i$$$ is minimum, $$$b_i$$$ must be maximized.

Observation 3: The maximum element of $$$b$$$ must be at least $$$mx_a - mn_a$$$, i.e. the difference between the maximum and minimum elements of $$$a$$$.

From Observation 3 and 1, we can set the maximum element of $$$b$$$ to $$$mx_a - mn_a, mx_a - mn_a + 1, ..., k$$$, which results to $$$k - (mx_a - mn_a) + 1$$$ different solutions.

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n, k; cin >> n >> k;
    int a[n], b[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    int s = -1;
    for (int i = 0; i < n; i++) {
        if (b[i] != -1) {
            if (s == -1) s = a[i] + b[i];
            else {
                if (s != a[i] + b[i]) {
                    cout << 0 << '\n';
                    return;
                }
            }
        }
    }
    if (s == -1) {
        sort(a, a+n);
        int mx = a[n-1] - a[0];
        cout << k - mx + 1 << '\n';
        return;
    }
    for (int i = 0; i < n; i++) {
        if (a[i] > s || s - a[i] > k) {
            cout << 0 << '\n';
            return;
        }
    }
    cout << 1 << '\n';
}
 
int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Amazing
• Good
• Average
• Bad
• Didn't Solve

There is a greedy strategy. Every time you see some flower in $$$a$$$, if its beauty is not less than the beauty of next flower you must pick from $$$b$$$, you will pick it. The answer is $$$0$$$ if we run the greedy without inserting a new flower in $$$a$$$ and still collecting all $$$m$$$ needed flowers.

Now, consider what inserting a new flower of beauty $$$k$$$ in $$$a$$$ will do. It will allow you to "skip" some flower listed in $$$b$$$, as you can place it anywhere in $$$a$$$ and just pick it up when necessary. Therefore, instead of inserting a new element, we can reconsider the problem as deleting some element listed in $$$b$$$. So, one slow solution would be to try deleting $$$b_1$$$, then running the greedy on $$$a$$$, and repeat for $$$b_2$$$, $$$b_3, ..., b_m$$$. Then, we can keep the minimum $$$b_i$$$ such that the greedy was successful when deleting that flower.

The solution is too slow. Instead, we can compute for every index $$$1 \le i \le m$$$ the minimum index $$$j$$$ such that if we run the greedy on the prefix $$$a_1, a_2, ..., a_j$$$, we will have collected flowers $$$b_1, b_2, ..., b_i$$$. Let this value for index $$$i$$$ of $$$b$$$ be $$$p_i$$$. Do the same for each suffix of $$$a$$$. Specifically, let $$$s_i$$$ be the maximum index $$$j$$$ such that if we run the greedy on the suffix $$$a_j, a_{j+1}, ..., a_n$$$ we would have collected the flowers $$$b_i, b_{i+1}, ..., b_m$$$. These values can be calculated with two pointers.

Now, we can delete $$$b_j$$$ if $$$p_{j-1} \lt s_{j+1}$$$ (to delete $$$b_1$$$, it must be that $$$s_{2} \gt 0$$$ and to delete $$$b_m$$$ that $$$p_{m-1} \le n$$$). We keep the minimum among all deletable values in $$$b$$$. If there does not exist such a value the answer is $$$-1$$$.

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 5;
 
int main(){
    int T; cin >> T;
    while(T--){
        int N, M; cin >> N >> M;
        vector<int> a(N), b(M);
        for(int i = 0; i < N; i++) cin >> a[i];
        for(int i = 0; i < M; i++) cin >> b[i];
        vector<int> backwards_match(M);
        int j = N - 1;
        for(int i = M - 1; i >= 0; i--){
            while(j >= 0 && a[j] < b[i]) j--;
            backwards_match[i] = j--;
        }
        vector<int> forwards_match(M);
        j = 0;
        for(int i = 0; i < M; i++){
            while(j < N && a[j] < b[i]) j++;
            forwards_match[i] = j++;
        }
        if(forwards_match.back() < N){
            cout << 0 << endl;
            continue;
        }
        int ans = INF;
        for(int i = 0; i < M; i++){
            int match_previous = i == 0 ? -1 : forwards_match[i - 1];
            int match_next = i + 1 == M ? N : backwards_match[i + 1];
            if(match_next > match_previous){
                ans = min(ans, b[i]);
            }
        }
        cout << (ans == INF ? -1 : ans) << "\n";
    }
}

• Amazing
• Good
• Average
• Bad
• Didn't Solve

Consider some permutation $$$p_1, p_2, ..., p_n$$$. Before answering queries, precompute the index of integer $$$i$$$ $$$(1 \le i \le n)$$$, suppose it is represented as $$$idx_i$$$.

Let's see how to answer some query $$$l, r, x$$$. Obviously, if $$$idx_x$$$ does not belong in the range $$$[l, r]$$$, the answer is $$$-1$$$. Otherwise, we want to somehow manipulate the elements so the binary search ends up checking $$$idx_x$$$.

Suppose the binary search is currently working on some range $$$[a, b]$$$. Let $$$m = \lfloor\frac{a + b}{2}\rfloor$$$. If $$$p_m = x$$$, we are done. Otherwise, consider the following cases:

• $$$p_m \lt x$$$ and $$$m \lt idx_x$$$: the binary search will continue on $$$[m+1, b]$$$, and since $$$idx_x$$$ belongs in that range, we simply let it continue. We must not swap this value.
• $$$p_m \lt x$$$ and $$$m \gt idx_x$$$: the binary search will continue on $$$[m+1, b]$$$, but $$$idx_x$$$ does not belong in that range. To fix this, we must replace $$$p_m$$$ with a value that is greater than $$$x$$$, in which case the search will continue on $$$[a, m-1]$$$.
• $$$p_m \gt x$$$ and $$$m \lt idx_x$$$: the binary search will continue on $$$[a, m-1]$$$, but $$$idx_x$$$ does not belong in that range. To fix this, we must replace $$$p_m$$$ with a value that is less than $$$x$$$, in which case the search will continue on $$$[m+1, b]$$$.
• $$$p_m \gt x$$$ and $$$m \gt idx_x$$$: the binary search will continue on $$$[a, m-1]$$$, and since $$$idx_x$$$ belongs in that range, we simply let it continue. We must not swap this value.

Keep doing this process until $$$p_m = x$$$. Suppose that the amount of integers less than $$$x$$$ needed are $$$s$$$, and the amount of integers greater than $$$x$$$ needed are $$$b$$$. In addition, let the values smaller than $$$x$$$ that we can't swap (because they already lead to the wanted direction) be denoted by $$$ss$$$ and those bigger as $$$bb$$$. There are $$$n - x$$$ greater values available in $$$p$$$, and $$$x-1$$$ smaller values available. Therefore, if $$$b \gt n - x - bb$$$ or $$$s \gt x - 1 - ss$$$, the answer is $$$-1$$$.

If the answer is not $$$-1$$$, we swap as many values as possible from $$$b$$$ and $$$s$$$ (which will be $$$\min{(b, s)} * 2$$$) and those that are still left after that (which will be $$$(\max{(b, s)} - \min{(b, s)}) * 2)$$$. The final answer is $$$(\max{(b, s)} - \min{(b, s)}) * 2 + \min{(b, s)} * 2$$$.

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
void solve() {
    int n, q; cin >> n >> q;
    int arr[n+1];
    vector<int> idx(n+1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        idx[arr[i]] = i;
    }
    while (q--) {
        int l, r, k; cin >> l >> r >> k;
        if (idx[k] > r || idx[k] < l) {
            cout << -1 << " ";
            continue;
        }
        int big = n - k, small = k - 1;
        int needBig = 0, needSmall = 0;
        int bigAv = n - k, smallAv = k - 1;
        int lo = l, hi = r;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (arr[mid] == k) break;
            if (mid < idx[k]) { // i want to go right
                if (k < arr[mid]) {
                    needSmall++;
                }
                else smallAv--;
                small--;
                lo = mid+1;
            }
            else { // i want to go left
                if (k > arr[mid]) { 
                    needBig++;
                }
                else bigAv--;
                big--;
                hi = mid-1;
            }
        }
        if (big < 0 || small < 0) {
            cout << -1 << " ";
            continue;
        }
        int ans = 2 * min(needBig, needSmall);
        int diff = abs(needBig - needSmall);
        if (needBig > needSmall) {
            if (bigAv < diff) cout << -1 << " ";
            else cout << ans + 2 * diff << " ";
        }
        else {
            if (smallAv < diff) cout << -1 << " ";
            else cout << ans + 2 * diff << " ";
        }
    }
}
 
signed main() {
    int t; cin >> t;
    while (t--){
      solve();
      cout << "\n";
    }
    return 0;
}

• Amazing
• Good
• Average
• Bad
• Didn't Solve

Each column can be broken down to $$$3$$$ components:

• If $$$a_i = 0$$$, the top-most component will contain $$$i-1$$$ zeros, the second component a single one, and the third component $$$n-i$$$ zeros.
• If $$$a_i = 1$$$, the top-most component will contain $$$i-1$$$ ones, the second component a single zero, and the third component $$$n-i$$$ ones.

The easiest way to visualize is with DSU. For each column, create $$$3$$$ components, and for each component implicitly store the number of $$$0$$$s in it. Now, we will try to merge all adjacent components that both consist of zeros. Consider the following transitions, for every $$$1 \lt i \le n$$$:

• If $$$a_i = 0$$$ and $$$a_{i-1} = 0$$$, then the top-most component of column $$$i-1$$$ will be merged with the top-most component of column $$$i$$$. The same goes for the two bottom-most components.
• If $$$a_i = 0$$$ and $$$a_{i-1} = 1$$$, then the top-most component of column $$$i$$$ will be merged with the top-most component of column $$$i-1$$$.
• If $$$a_i = 1$$$ and $$$a_{i-1} = 0$$$, then the bottom-most component of column $$$i$$$ will be merged with the bottom-most component of column $$$i-1$$$.
• If $$$a_i = 1$$$ and $$$a_{i-1} = 1$$$, we merge nothing.

After we finish the merging, we just take the component with the maximum number of zeros, which will be the answer to this problem. Note that you do not actually have to use DSU; we only care about the sizes and not the representatives, so we can also use simple prefix sums.

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
void solve() {
    int n; cin >> n;
    string s; cin >> s;
    s = " " + s;
    vector<int> top(n+1, 0), bot(n+1, 0);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '1') {
            top[i] = bot[i-1] + 1;
        }
        else {
            top[i] = top[i-1] + (i - 1);
            bot[i] = bot[i-1] + (n - i);
        }
        ans = max(ans, max(top[i], bot[i]));
    }
    cout << ans << "\n";
}
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }
 
struct DSU{
    vector<int> p, sz;
    vector<ll> score;
    
    DSU(int n){
        p.assign(n, 0);
        sz.assign(n, 1);
        score.assign(n, 0);
        
        for (int i = 0; i < n; i++) p[i] = i;
    }
    
    int find(int u){
        if (p[u] == u) return u;
        p[u] = find(p[u]);
        return p[u];
    }
    
    void unite(int u, int v){
        u = find(u);
        v = find(v);
        if (u == v) return;
        
        if (sz[u] < sz[v]) swap(u, v);
        p[v] = u;
        sz[u] += sz[v];
        score[u] += score[v];
    }
    
    bool same(int u, int v){
        return find(u) == find(v);
    }
    
    int size(int u){
        u = find(u);
        return sz[u];
    }
};
 
void solve(){
    int n;
    cin >> n;
 
    string s;
    cin >> s;
    
    DSU dsu(2 * n);
    vector<array<int, 2>> prev;
    for (int i = 0; i < n; i++){
        if (s[i] == '1'){
            dsu.score[2 * i] = 1;
            dsu.unite(2 * i, 2 * i + 1);
            
            for (int j = 0; j < prev.size(); j++){
                int l = prev[j][0];
                int r = prev[j][1];
                if (i >= l && i <= r)
                    dsu.unite(2 * i, 2 * (i - 1) + j);
            }
            prev = {{i, i}};
            continue;
        }
 
        vector<array<int, 2>> nxt = {{0, i - 1}, {i + 1, n - 1}};
        for (int j = 0; j < nxt.size(); j++){
            auto [l, r] = nxt[j];
            dsu.score[2 * i + j] = r - l + 1;
        }
 
        for (int j = 0; j < prev.size(); j++){
            for (int k = 0; k < nxt.size(); k++){
                auto [l1, r1] = prev[j];
                auto [l2, r2] = nxt[k];
 
                if (l2 > r1 || r2 < l1)
                    continue;
 
                dsu.unite(2 * i + k, 2 * (i - 1) + j);
            }
        }
        prev = nxt;
    }
 
    ll ans = 0;
    for (int i = 0; i < 2 * n; i++)
        ans = max(ans, dsu.score[i]);
    cout << ans << "\n";
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

• Amazing
• Good
• Average
• Bad
• Didn't Solve

For some node $$$u$$$, let $$$v_u$$$ be its value and $$$s_u$$$ be the sum of the values of all nodes on the simple path from the root of the tree to node $$$u$$$ ($$$s_u$$$ will also be referenced as "the sum of node $$$u$$$" for the purposes of this solution). Also, let $$$p_u$$$ be the parent of node $$$u$$$ (if $$$u$$$ is not the root).

Suppose that we know which node is the root of the tree. Then, we can make $$$n$$$ queries to find $$$s_1, s_2, ..., s_n$$$, which is sufficient to figure out $$$v_1, v_2, ..., v_n$$$: it holds that $$$s_u = s_{p_u} + v_u$$$, therefore $$$v_u = s_u - s_{p_u}$$$.

Then, we have $$$200$$$ queries left to find the actual root of the tree. Consider some node $$$u$$$, and all of its neighbor nodes $$$c_1, c_2, ..., c_k$$$.

Observation 1: Toggling the value of node $$$u$$$ will change the sum of every adjacent node to $$$u$$$ that is not the parent.

Observation 2: We can find the parent of node $$$u$$$ within $$$3\log k$$$ queries. Consider doing binary search to find which node does not change its sum when toggling the value of $$$u$$$. In order to check if the prefix $$$c_1, c_2, ..., c_m$$$ includes the parent of $$$u$$$, we do the following: query for $$$s1 = s_{c_1} + s_{c_2} + ... + s_{c_m}$$$, toggle the value of $$$u$$$, and query for $$$s2 = s_{c_1}' + s_{c_2}' + ... + s_{c_m}'$$$ again. Let $$$D = |s1 - s2|$$$. From Observation 1, if every node among $$$c_1, c_2, ..., c_m$$$ changed its value, then $$$D = 2m$$$, so we know that the parent does not belong in that prefix. Otherwise, there is a node that did not change its sum, so we can continue our binary search on that prefix. This takes $$$3$$$ queries performed $$$\log k$$$ times. Note that if we never find the parent, it must mean that $$$u$$$ is the root of the tree.

Since the tree is a star, if we find the parent of node $$$1$$$, we will find the root. If there does not exist a parent, then $$$1$$$ is the root. The problem has been solved in $$$n + 3 \log(n)$$$ queries, which comfortably fits the query limit.

There are a lot of other (better) solutions for this version (for example, this solution), but this solution helps best for coming up with the idea for G2.

#include <bits/stdc++.h>
using i64 = long long;
 
void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n+1), son(n-1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        std::cin >> u >> v;
        son[i-1] = i + 1;
    }
    int Q = 0;
    auto ask = [&](int op, const std::vector<int> &v) {
        if (++Q > n + 200) {
            assert(false);
        }
        std::cout << "? " << op;
        if (op == 1) {
            std::cout << ' ' << v.size();
            for (auto u: v) std::cout << ' ' << u;
            std::cout << std::endl;
            int res = 0;
            std::cin >> res;
            return res;
        } else {
            std::cout << ' ' << v[0] << std::endl;
            return 0;
        }
    };
    int rt = 0;
    int bef = ask(1, son);
    ask(2, std::vector<int>{1});
    int af = ask(1, son);
    if (std::abs(bef - af) == 2 * son.size()) {
        rt = 1;
    } else {
        int l = 0, r = son.size() - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            std::vector<int> query(son.begin() + l, son.begin() + mid + 1);
            int bef = ask(1, query);
            ask(2, std::vector<int>{1});
            int af = ask(1, query);
            if (std::abs(bef - af) != 2 * (mid - l + 1)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        rt = son[l];
    }
    for (int i = 1; i <= n; ++i) {
        a[i] = ask(1, std::vector<int>{i});
    }
    for (int i = 2; i <= n; ++i) {
        if (rt != i) {
            a[i] -= a[1];
        }
    }
    if (rt > 1) a[1] -= a[rt];
    std::cout << '!';
    for (int i = 1; i <= n; ++i) {
        std::cout << ' ' << a[i];
    }
    std::cout << std::endl;
}
 
int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    std::cin >> T;
    while (T--) solve();
    return 0;
}

• Amazing
• Good
• Average
• Bad
• Didn't Solve

Read the solution to the Easy Version first.

Obviously, if we know the parent of some node, we know which nodes are under that node's subtree, so we never have to consider them as candidates for the root of the tree. Let's use this to choose nodes in a way such that each time we eliminate as many candidates as possible, even in the worst case.

Specifically, consider querying for the centroid of the tree (a centroid of a tree is a node that if it is deleted, every connected component left has size no more than half of the original tree). When querying for the centroid, there are two cases: either it is the root of the tree, in which case we are finished, or we find its parent, which eliminates at least half of the current candidates. Then, we delete all nodes that could not possibly be the root, and query for the new centroid.

Since the candidates get halved each time, we repeat the above process no more than $$$\log n$$$ times. In the absolute worst case (which is not realistic), we make $$$3\log (n) + 3\log (\frac{n}{2}) + 3\log (\frac{n}{4}) + ... + 3$$$ queries. For $$$n = 1000$$$, this is about $$$165$$$ queries. I do want to stress that this case is impossible; the $$$200$$$ queries are pretty loose but I want to allow a lot of different solutions (there are some even better ones than the one I described here, feel free to describe better solutions in the comments).

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
vector<vector<int>> tree, cd;
vector<int> sub, val;
vector<bool> del;
int n, cdRoot = -1;
 
int ask(vector<int> a) {
    int k = a.size();
    cout << "? 1 " << k << " ";
    for (auto x: a) {
        cout << x << " ";
    }
    cout << endl;
    int ans; cin >> ans;
    return ans;
}
 
void toggle(int u) {
    cout << "? 2 " << u << endl;
}
 
void answer(vector<int> ans) {
    cout << "! ";
    for (int i = 1; i <= n; i++) cout << ans[i] << " ";
    cout << endl;
}
 
void calc_sums(int node, int par = 0) {
    sub[node] = 0;
    if (del[node]) return;
    for (auto next: tree[node]) {
        if (next == par) continue;
        calc_sums(next, node);
        sub[node] += sub[next];
    }
    sub[node]++;
}
 
int find_centroid(int node, int sz, int par = 0) {
    for (auto next: tree[node]) {
        if (next == par || del[next]) continue;
        if (sub[next] * 2 >= sz) return find_centroid(next, sz, node);
    }
    return node;
}
 
void build(int node, int prev) {
    cd[prev].push_back(node);
    del[node] = true;
    for (auto next: tree[node]) {
        if (del[next]) continue;
        calc_sums(next, node);
        int cent = find_centroid(next, sub[next], node);
        build(cent, node);
    }
}
 
bool inspect(vector<int> a, int tog) {
    int b4 = ask(a);
    toggle(tog);
    int aft = ask(a);
    int k = a.size();
    int must = b4;
    if (aft < b4) {
        must -= 2 * k;
    }
    else must += 2 * k;
    if (aft != must) return true;
    else return false;
}
 
int find_sus(vector<int> a, int tog) {
    int k = a.size();
    int lo = 0, hi = k-1;
    int ans = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        vector<int> qr;
        for (int j = 0; j <= mid; j++) {
            qr.push_back(a[j]);
        }
        if (inspect(qr, tog)) {
            ans = mid;
            hi = mid-1;
        }
        else lo = mid+1;
    }
    return ans; 
}
 
int find_root(int node, int par = 0) {
    if (cd[node].empty()) return node;
    vector<int> ch;
    for (auto next: cd[node]) {
        if (next == par) continue;
        ch.push_back(next);
    }
    int sus = find_sus(ch, node);
    if (sus == -1) return node;
    return find_root(ch[sus], node);
}
 
void find_vals(int node, int par = 0, int above = 0) {
    val[node] -= above;
    above += val[node];
    for (auto next: tree[node]) {
        if (next != par) {
            find_vals(next, node, above);
        }
    }
}
 
void solve() {
    cin >> n;
    cd.assign(n+1, {});
    tree.assign(n+1, {});
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }    
    del.assign(n+1, false);
    sub.assign(n+1, 0);
    calc_sums(1);
    cdRoot = find_centroid(1, n);
    build(cdRoot, 0);
    int root = find_root(cdRoot);
    val.resize(n+1);
    for (int i = 1; i <= n; i++) {
        val[i] = ask({i});
    }
    find_vals(root);
    answer(val);
}
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Amazing
• Good
• Average
• Bad
• Didn't Solve