codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2106.md (26893B)


      1 Source: https://codeforces.com/blog/entry/142254
      2 
      3 Thanks for the participation. I hope you enjoyed the problems, or at the very least learned something new.
      4 
      5 **Rate Contest Quality**
      6 
      7 * Amazing
      8 * Good
      9 * Average
     10 * Bad
     11 
     12 **Rate Contest Difficulty**
     13 
     14 * Very Hard
     15 * Hard
     16 * Average
     17 * Easy
     18 * Very Easy
     19 
     20 **Favorite Problem**
     21 
     22 * A
     23 * B
     24 * C
     25 * D
     26 * E
     27 * F
     28 * G1
     29 * G2
     30 
     31 **Worst Problem**
     32 
     33 * A
     34 * B
     35 * C
     36 * D
     37 * E
     38 * F
     39 * G1
     40 * G2
     41 
     42 ~~The codes will be posted after the hacking phase is over.~~ Codes have been posted.
     43 
     44 [Problem A — DR. TC](https://codeforces.com/contest/2106/problem/A)
     45 
     46 (Author & Analysis: [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv"))
     47 
     48 **Solution**
     49 
     50 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).
     51 
     52 **Implementation**
     53 
     54 ```
     55 #include <bits/stdc++.h>
     56 using namespace std;
     57  
     58 void solve() {
     59     int n; cin >> n;
     60     string s; cin >> s;
     61     int ans = 0;
     62     for (auto x: s) {
     63         if (x == '0') ans++;
     64         else ans += n - 1;
     65     }
     66     cout << ans << '\n';
     67 }
     68  
     69 int main() {
     70     int t; cin >> t;
     71     while (t--) solve();
     72     return 0;
     73 }
     74 ```
     75 
     76 **Rate the Problem**
     77 
     78 * Amazing
     79 * Good
     80 * Average
     81 * Bad
     82 * Didn't Solve
     83 
     84 [Problem B — ST. CHROMA](https://codeforces.com/contest/2106/problem/B)
     85 
     86 (Author & Analysis: [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv"))
     87 
     88 **Solution**
     89 
     90 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.
     91 
     92 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$.
     93 
     94 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]$.
     95 
     96 **Implementation**
     97 
     98 ```
     99 #include <bits/stdc++.h>
    100 using namespace std;
    101  
    102 void solve() {
    103     int n, x; cin >> n >> x;
    104     for (int i = 0; i < x; i++) cout << i << " ";
    105     for (int i = x+1; i < n; i++) cout << i << " ";
    106     if (x < n) cout << x;
    107     cout << '\n';
    108 }
    109  
    110 int main() {
    111     int t; cin >> t;
    112     while (t--) solve();
    113     return 0;
    114 }
    115 ```
    116 
    117 **Rate the Problem**
    118 
    119 * Amazing
    120 * Good
    121 * Average
    122 * Bad
    123 * Didn't Solve
    124 
    125 [Problem C — CHERRY BOMB](https://codeforces.com/contest/2106/problem/C)
    126 
    127 (Author & Analysis: [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv"))
    128 
    129 **Solution**
    130 
    131 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$.
    132 
    133 **Observation 1:** If we know every element of $a$, and we know $s$, we can uniquely determine the elements of $b$.
    134 
    135 We split the problem into two cases.
    136 
    137 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.
    138 
    139 The second case is if every element of $b$ is missing:
    140 
    141 **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.
    142 
    143 **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$.
    144 
    145 **Proof**
    146 
    147 Suppose that the maximum of $b$ is positioned at index $i$, and $b_i \lt mx_a - mn_a$. From Observation 2, $a_i = mn_a$, since the position of the maximum element of $b$ is the position of the minimum element of $a$. Then $s = a_i + b_i$, and $a_i + b_i \lt a_i + mx_a - mn_a$ (since $b_i \lt mx_a - mn_a$), so $s \lt mn_a + mx_a - mn_a = mx_a$ (since $a_i = mn_a$). However, $s \lt mx_a$ cannot hold (since elements of $b$ cannot be negative), therefore this is a contradiciton.
    148 
    149 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.
    150 
    151 **Implementation**
    152 
    153 ```
    154 #include <bits/stdc++.h>
    155 using namespace std;
    156  
    157 void solve() {
    158     int n, k; cin >> n >> k;
    159     int a[n], b[n];
    160     for (int i = 0; i < n; i++) cin >> a[i];
    161     for (int i = 0; i < n; i++) cin >> b[i];
    162     int s = -1;
    163     for (int i = 0; i < n; i++) {
    164         if (b[i] != -1) {
    165             if (s == -1) s = a[i] + b[i];
    166             else {
    167                 if (s != a[i] + b[i]) {
    168                     cout << 0 << '\n';
    169                     return;
    170                 }
    171             }
    172         }
    173     }
    174     if (s == -1) {
    175         sort(a, a+n);
    176         int mx = a[n-1] - a[0];
    177         cout << k - mx + 1 << '\n';
    178         return;
    179     }
    180     for (int i = 0; i < n; i++) {
    181         if (a[i] > s || s - a[i] > k) {
    182             cout << 0 << '\n';
    183             return;
    184         }
    185     }
    186     cout << 1 << '\n';
    187 }
    188  
    189 int main() {
    190     int t; cin >> t;
    191     while (t--) solve();
    192     return 0;
    193 }
    194 ```
    195 
    196 **Rate the Problem**
    197 
    198 * Amazing
    199 * Good
    200 * Average
    201 * Bad
    202 * Didn't Solve
    203 
    204 [Problem D — IGOR / FLOWER BOY](https://codeforces.com/contest/2106/problem/D)
    205 
    206 (Author: [cry](/profile/cry "International Master cry"), Analysis: [cowthecow](/profile/cowthecow "Expert cowthecow"))
    207 
    208 **Solution**
    209 
    210 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.
    211 
    212 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.
    213 
    214 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.
    215 
    216 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$.
    217 
    218 **Implementation**
    219 
    220 ```
    221 #include <bits/stdc++.h>
    222 using namespace std;
    223 const int INF = 1e9 + 5;
    224  
    225 int main(){
    226     int T; cin >> T;
    227     while(T--){
    228         int N, M; cin >> N >> M;
    229         vector<int> a(N), b(M);
    230         for(int i = 0; i < N; i++) cin >> a[i];
    231         for(int i = 0; i < M; i++) cin >> b[i];
    232         vector<int> backwards_match(M);
    233         int j = N - 1;
    234         for(int i = M - 1; i >= 0; i--){
    235             while(j >= 0 && a[j] < b[i]) j--;
    236             backwards_match[i] = j--;
    237         }
    238         vector<int> forwards_match(M);
    239         j = 0;
    240         for(int i = 0; i < M; i++){
    241             while(j < N && a[j] < b[i]) j++;
    242             forwards_match[i] = j++;
    243         }
    244         if(forwards_match.back() < N){
    245             cout << 0 << endl;
    246             continue;
    247         }
    248         int ans = INF;
    249         for(int i = 0; i < M; i++){
    250             int match_previous = i == 0 ? -1 : forwards_match[i - 1];
    251             int match_next = i + 1 == M ? N : backwards_match[i + 1];
    252             if(match_next > match_previous){
    253                 ans = min(ans, b[i]);
    254             }
    255         }
    256         cout << (ans == INF ? -1 : ans) << "\n";
    257     }
    258 }
    259 ```
    260 
    261 **Rate the Problem**
    262 
    263 * Amazing
    264 * Good
    265 * Average
    266 * Bad
    267 * Didn't Solve
    268 
    269 [Problem E — WOLF](https://codeforces.com/contest/2106/problem/E)
    270 
    271 (Author: [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv"), Analysis: [cowthecow](/profile/cowthecow "Expert cowthecow"))
    272 
    273 **Solution**
    274 
    275 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$.
    276 
    277 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$.
    278 
    279 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:
    280 
    281 * $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**.
    282 * $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]$.
    283 * $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]$.
    284 * $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**.
    285 
    286 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$.
    287 
    288 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$.
    289 
    290 **Implementation**
    291 
    292 ```
    293 #include <bits/stdc++.h>
    294 using namespace std;
    295 #define int long long
    296  
    297 void solve() {
    298     int n, q; cin >> n >> q;
    299     int arr[n+1];
    300     vector<int> idx(n+1, 0);
    301     for (int i = 1; i <= n; i++) {
    302         cin >> arr[i];
    303         idx[arr[i]] = i;
    304     }
    305     while (q--) {
    306         int l, r, k; cin >> l >> r >> k;
    307         if (idx[k] > r || idx[k] < l) {
    308             cout << -1 << " ";
    309             continue;
    310         }
    311         int big = n - k, small = k - 1;
    312         int needBig = 0, needSmall = 0;
    313         int bigAv = n - k, smallAv = k - 1;
    314         int lo = l, hi = r;
    315         while (lo <= hi) {
    316             int mid = (lo + hi) / 2;
    317             if (arr[mid] == k) break;
    318             if (mid < idx[k]) { // i want to go right
    319                 if (k < arr[mid]) {
    320                     needSmall++;
    321                 }
    322                 else smallAv--;
    323                 small--;
    324                 lo = mid+1;
    325             }
    326             else { // i want to go left
    327                 if (k > arr[mid]) { 
    328                     needBig++;
    329                 }
    330                 else bigAv--;
    331                 big--;
    332                 hi = mid-1;
    333             }
    334         }
    335         if (big < 0 || small < 0) {
    336             cout << -1 << " ";
    337             continue;
    338         }
    339         int ans = 2 * min(needBig, needSmall);
    340         int diff = abs(needBig - needSmall);
    341         if (needBig > needSmall) {
    342             if (bigAv < diff) cout << -1 << " ";
    343             else cout << ans + 2 * diff << " ";
    344         }
    345         else {
    346             if (smallAv < diff) cout << -1 << " ";
    347             else cout << ans + 2 * diff << " ";
    348         }
    349     }
    350 }
    351  
    352 signed main() {
    353     int t; cin >> t;
    354     while (t--){
    355       solve();
    356       cout << "\n";
    357     }
    358     return 0;
    359 }
    360 ```
    361 
    362 **Rate the Problem**
    363 
    364 * Amazing
    365 * Good
    366 * Average
    367 * Bad
    368 * Didn't Solve
    369 
    370 [Problem F — GOBLIN](https://codeforces.com/contest/2106/problem/F)
    371 
    372 (Author & Analysis: [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv"))
    373 
    374 **Solution**
    375 
    376 Each column can be broken down to $3$ components:
    377 
    378 * 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.
    379 * 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.
    380 
    381 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$:
    382 
    383 * 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.
    384 * 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$.
    385 * 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$.
    386 * If $a_i = 1$ and $a_{i-1} = 1$, we merge nothing.
    387 
    388 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.
    389 
    390 **Implementation (Prefix Sums)**
    391 
    392 ```
    393 #include <bits/stdc++.h>
    394 using namespace std;
    395 #define int long long
    396  
    397 void solve() {
    398     int n; cin >> n;
    399     string s; cin >> s;
    400     s = " " + s;
    401     vector<int> top(n+1, 0), bot(n+1, 0);
    402     int ans = 0;
    403     for (int i = 1; i <= n; i++) {
    404         if (s[i] == '1') {
    405             top[i] = bot[i-1] + 1;
    406         }
    407         else {
    408             top[i] = top[i-1] + (i - 1);
    409             bot[i] = bot[i-1] + (n - i);
    410         }
    411         ans = max(ans, max(top[i], bot[i]));
    412     }
    413     cout << ans << "\n";
    414 }
    415  
    416 signed main() {
    417     ios_base::sync_with_stdio(0);
    418     cin.tie(0);
    419     int t; cin >> t;
    420     while (t--) solve();
    421     return 0;
    422 }
    423 ```
    424 
    425 **Implementation (DSU)**
    426 
    427 ```
    428 #include<bits/stdc++.h>
    429 using namespace std;
    430 typedef long long ll;
    431 #define debug(x) cout << #x << " = " << x << "\n";
    432 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
    433 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    434 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
    435 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }
    436  
    437 struct DSU{
    438     vector<int> p, sz;
    439     vector<ll> score;
    440     
    441     DSU(int n){
    442         p.assign(n, 0);
    443         sz.assign(n, 1);
    444         score.assign(n, 0);
    445         
    446         for (int i = 0; i < n; i++) p[i] = i;
    447     }
    448     
    449     int find(int u){
    450         if (p[u] == u) return u;
    451         p[u] = find(p[u]);
    452         return p[u];
    453     }
    454     
    455     void unite(int u, int v){
    456         u = find(u);
    457         v = find(v);
    458         if (u == v) return;
    459         
    460         if (sz[u] < sz[v]) swap(u, v);
    461         p[v] = u;
    462         sz[u] += sz[v];
    463         score[u] += score[v];
    464     }
    465     
    466     bool same(int u, int v){
    467         return find(u) == find(v);
    468     }
    469     
    470     int size(int u){
    471         u = find(u);
    472         return sz[u];
    473     }
    474 };
    475  
    476 void solve(){
    477     int n;
    478     cin >> n;
    479  
    480     string s;
    481     cin >> s;
    482     
    483     DSU dsu(2 * n);
    484     vector<array<int, 2>> prev;
    485     for (int i = 0; i < n; i++){
    486         if (s[i] == '1'){
    487             dsu.score[2 * i] = 1;
    488             dsu.unite(2 * i, 2 * i + 1);
    489             
    490             for (int j = 0; j < prev.size(); j++){
    491                 int l = prev[j][0];
    492                 int r = prev[j][1];
    493                 if (i >= l && i <= r)
    494                     dsu.unite(2 * i, 2 * (i - 1) + j);
    495             }
    496             prev = {{i, i}};
    497             continue;
    498         }
    499  
    500         vector<array<int, 2>> nxt = {{0, i - 1}, {i + 1, n - 1}};
    501         for (int j = 0; j < nxt.size(); j++){
    502             auto [l, r] = nxt[j];
    503             dsu.score[2 * i + j] = r - l + 1;
    504         }
    505  
    506         for (int j = 0; j < prev.size(); j++){
    507             for (int k = 0; k < nxt.size(); k++){
    508                 auto [l1, r1] = prev[j];
    509                 auto [l2, r2] = nxt[k];
    510  
    511                 if (l2 > r1 || r2 < l1)
    512                     continue;
    513  
    514                 dsu.unite(2 * i + k, 2 * (i - 1) + j);
    515             }
    516         }
    517         prev = nxt;
    518     }
    519  
    520     ll ans = 0;
    521     for (int i = 0; i < 2 * n; i++)
    522         ans = max(ans, dsu.score[i]);
    523     cout << ans << "\n";
    524 }
    525  
    526 int main(){
    527     ios::sync_with_stdio(false);
    528     cin.tie(0);
    529     cout.tie(0);
    530     
    531     int t;
    532     cin >> t;
    533     while (t--) solve();
    534 }
    535 ```
    536 
    537 **Rate the Problem**
    538 
    539 * Amazing
    540 * Good
    541 * Average
    542 * Bad
    543 * Didn't Solve
    544 
    545 [Problem G1 — BAUDELAIRE (Easy Version)](https://codeforces.com/contest/2106/problem/G1)
    546 
    547 (Author & Analysis: [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv"))
    548 
    549 **Solution**
    550 
    551 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).
    552 
    553 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}$.
    554 
    555 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$.
    556 
    557 **Observation 1:** Toggling the value of node $u$ will change the sum of every adjacent node to $u$ that is not the parent.
    558 
    559 **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.
    560 
    561 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.
    562 
    563 There are a lot of other (better) solutions for this version (for example, [this solution](https://codeforces.com/blog/entry/142254?#comment-1269097)), but this solution helps best for coming up with the idea for G2.
    564 
    565 **Implementation**
    566 
    567 ```
    568 #include <bits/stdc++.h>
    569 using i64 = long long;
    570  
    571 void solve() {
    572     int n;
    573     std::cin >> n;
    574     std::vector<int> a(n+1), son(n-1);
    575     for (int i = 1; i < n; ++i) {
    576         int u, v;
    577         std::cin >> u >> v;
    578         son[i-1] = i + 1;
    579     }
    580     int Q = 0;
    581     auto ask = [&](int op, const std::vector<int> &v) {
    582         if (++Q > n + 200) {
    583             assert(false);
    584         }
    585         std::cout << "? " << op;
    586         if (op == 1) {
    587             std::cout << ' ' << v.size();
    588             for (auto u: v) std::cout << ' ' << u;
    589             std::cout << std::endl;
    590             int res = 0;
    591             std::cin >> res;
    592             return res;
    593         } else {
    594             std::cout << ' ' << v[0] << std::endl;
    595             return 0;
    596         }
    597     };
    598     int rt = 0;
    599     int bef = ask(1, son);
    600     ask(2, std::vector<int>{1});
    601     int af = ask(1, son);
    602     if (std::abs(bef - af) == 2 * son.size()) {
    603         rt = 1;
    604     } else {
    605         int l = 0, r = son.size() - 1;
    606         while (l < r) {
    607             int mid = l + (r - l) / 2;
    608             std::vector<int> query(son.begin() + l, son.begin() + mid + 1);
    609             int bef = ask(1, query);
    610             ask(2, std::vector<int>{1});
    611             int af = ask(1, query);
    612             if (std::abs(bef - af) != 2 * (mid - l + 1)) {
    613                 r = mid;
    614             } else {
    615                 l = mid + 1;
    616             }
    617         }
    618         rt = son[l];
    619     }
    620     for (int i = 1; i <= n; ++i) {
    621         a[i] = ask(1, std::vector<int>{i});
    622     }
    623     for (int i = 2; i <= n; ++i) {
    624         if (rt != i) {
    625             a[i] -= a[1];
    626         }
    627     }
    628     if (rt > 1) a[1] -= a[rt];
    629     std::cout << '!';
    630     for (int i = 1; i <= n; ++i) {
    631         std::cout << ' ' << a[i];
    632     }
    633     std::cout << std::endl;
    634 }
    635  
    636 int main() {
    637     std::cin.tie(nullptr)->sync_with_stdio(false);
    638     int T = 1;
    639     std::cin >> T;
    640     while (T--) solve();
    641     return 0;
    642 }
    643 ```
    644 
    645 **Rate the Problem**
    646 
    647 * Amazing
    648 * Good
    649 * Average
    650 * Bad
    651 * Didn't Solve
    652 
    653 [Problem G2 — BAUDELAIRE (Hard Version)](https://codeforces.com/contest/2106/problem/G2)
    654 
    655 (Author & Analysis: [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv"))
    656 
    657 **Solution**
    658 
    659 Read the solution to the Easy Version first.
    660 
    661 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.
    662 
    663 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.
    664 
    665 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).
    666 
    667 **Implementation**
    668 
    669 ```
    670 #include <bits/stdc++.h>
    671 using namespace std;
    672 #define int long long
    673  
    674 vector<vector<int>> tree, cd;
    675 vector<int> sub, val;
    676 vector<bool> del;
    677 int n, cdRoot = -1;
    678  
    679 int ask(vector<int> a) {
    680     int k = a.size();
    681     cout << "? 1 " << k << " ";
    682     for (auto x: a) {
    683         cout << x << " ";
    684     }
    685     cout << endl;
    686     int ans; cin >> ans;
    687     return ans;
    688 }
    689  
    690 void toggle(int u) {
    691     cout << "? 2 " << u << endl;
    692 }
    693  
    694 void answer(vector<int> ans) {
    695     cout << "! ";
    696     for (int i = 1; i <= n; i++) cout << ans[i] << " ";
    697     cout << endl;
    698 }
    699  
    700 void calc_sums(int node, int par = 0) {
    701     sub[node] = 0;
    702     if (del[node]) return;
    703     for (auto next: tree[node]) {
    704         if (next == par) continue;
    705         calc_sums(next, node);
    706         sub[node] += sub[next];
    707     }
    708     sub[node]++;
    709 }
    710  
    711 int find_centroid(int node, int sz, int par = 0) {
    712     for (auto next: tree[node]) {
    713         if (next == par || del[next]) continue;
    714         if (sub[next] * 2 >= sz) return find_centroid(next, sz, node);
    715     }
    716     return node;
    717 }
    718  
    719 void build(int node, int prev) {
    720     cd[prev].push_back(node);
    721     del[node] = true;
    722     for (auto next: tree[node]) {
    723         if (del[next]) continue;
    724         calc_sums(next, node);
    725         int cent = find_centroid(next, sub[next], node);
    726         build(cent, node);
    727     }
    728 }
    729  
    730 bool inspect(vector<int> a, int tog) {
    731     int b4 = ask(a);
    732     toggle(tog);
    733     int aft = ask(a);
    734     int k = a.size();
    735     int must = b4;
    736     if (aft < b4) {
    737         must -= 2 * k;
    738     }
    739     else must += 2 * k;
    740     if (aft != must) return true;
    741     else return false;
    742 }
    743  
    744 int find_sus(vector<int> a, int tog) {
    745     int k = a.size();
    746     int lo = 0, hi = k-1;
    747     int ans = -1;
    748     while (lo <= hi) {
    749         int mid = (lo + hi) / 2;
    750         vector<int> qr;
    751         for (int j = 0; j <= mid; j++) {
    752             qr.push_back(a[j]);
    753         }
    754         if (inspect(qr, tog)) {
    755             ans = mid;
    756             hi = mid-1;
    757         }
    758         else lo = mid+1;
    759     }
    760     return ans; 
    761 }
    762  
    763 int find_root(int node, int par = 0) {
    764     if (cd[node].empty()) return node;
    765     vector<int> ch;
    766     for (auto next: cd[node]) {
    767         if (next == par) continue;
    768         ch.push_back(next);
    769     }
    770     int sus = find_sus(ch, node);
    771     if (sus == -1) return node;
    772     return find_root(ch[sus], node);
    773 }
    774  
    775 void find_vals(int node, int par = 0, int above = 0) {
    776     val[node] -= above;
    777     above += val[node];
    778     for (auto next: tree[node]) {
    779         if (next != par) {
    780             find_vals(next, node, above);
    781         }
    782     }
    783 }
    784  
    785 void solve() {
    786     cin >> n;
    787     cd.assign(n+1, {});
    788     tree.assign(n+1, {});
    789     for (int i = 1; i < n; i++) {
    790         int u, v; cin >> u >> v;
    791         tree[u].push_back(v);
    792         tree[v].push_back(u);
    793     }    
    794     del.assign(n+1, false);
    795     sub.assign(n+1, 0);
    796     calc_sums(1);
    797     cdRoot = find_centroid(1, n);
    798     build(cdRoot, 0);
    799     int root = find_root(cdRoot);
    800     val.resize(n+1);
    801     for (int i = 1; i <= n; i++) {
    802         val[i] = ask({i});
    803     }
    804     find_vals(root);
    805     answer(val);
    806 }
    807  
    808 signed main() {
    809     ios_base::sync_with_stdio(0);
    810     cin.tie(0);
    811     int t; cin >> t;
    812     while (t--) solve();
    813     return 0;
    814 }
    815 ```
    816 
    817 **Rate the Problem**
    818 
    819 * Amazing
    820 * Good
    821 * Average
    822 * Bad
    823 * Didn't Solve