codeforces-scrape

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

2127.md (52847B)


      1 Source: https://codeforces.com/blog/entry/145357
      2 
      3 ### ✨ **Hope you enjoyed the problems!** ✨
      4 
      5 [2127A - Mix Mex Max](/contest/2127/problem/A)  
      6  **Idea:** [Bahamin](/profile/Bahamin "Master Bahamin")  
      7  **Preparation:** [Hamed_Ghaffari](/profile/Hamed_Ghaffari "Grandmaster Hamed_Ghaffari")
      8 
      9 **Hints**
     10 
     11 **Hint 1**
     12 
     13 What happens if $\operatorname{mex}([a_i, a_{i+1}, a_{i+2}]) = 0$?
     14 
     15 **Hint 2**
     16 
     17 Now what happens if $\operatorname{mex}([a_i, a_{i+1}, a_{i+2}]) \neq 0$?
     18 
     19 **Solution**
     20 
     21 Let's see when does $\operatorname{mex}([a_i, a_{i+1}, a_{i+2}])$ equal $\max([a_i, a_{i+1}, a_{i+2}]) - \min([a_i, a_{i+1}, a_{i+2}])$.
     22 
     23 **Case 1:** $\operatorname{mex}([a_i, a_{i+1}, a_{i+2}]) = 0$
     24 
     25 This implies that all numbers are equal and non-zero, since otherwise $\min$ would be less than $\max$ and the difference wouldn't be $0$.
     26 
     27 **Case 2:** $\operatorname{mex}([a_i, a_{i+1}, a_{i+2}]) \neq 0$
     28 
     29 In this case $\min([a_i, a_{i+1}, a_{i+2}])$ should be $0$ because $0$ is in the sequence. So $\operatorname{mex}([a_i, a_{i+1}, a_{i+2}]) = \max([a_i, a_{i+1}, a_{i+2}])$ but this is not possible, since $\operatorname{mex}([a_i, a_{i+1}, a_{i+2}])$ should not be among $a_i$, $a_{i+1}$, or $a_{i+2}$.
     30 
     31 So an array is good if all elements are equal and non-zero. Remove every $-1$ from $a$, then check whether all remaining elements are equal and non-zero.
     32 
     33 **Code**
     34 
     35 ```
     36 #include <bits/stdc++.h>
     37 
     38 using namespace std;
     39 
     40 int main() {
     41     int tc;
     42     cin >> tc;
     43     while (tc--) {
     44         int n;
     45         cin>>n;
     46         vector<int> v(n);
     47         for (int i = 0; i < n; i++) cin >> v[i];
     48         set<int> s(v.begin(), v.end());
     49         
     50         s.erase(-1);
     51         if (s.size()<=1 && !s.count(0)) cout<<"YES"<<endl;
     52         else cout<<"NO"<<endl;
     53     }
     54 }
     55 ```
     56 
     57 ---
     58 
     59 [2127B - Hamiiid, Haaamid... Hamid?](/contest/2127/problem/B)  
     60  **Idea:** [_R00T](/profile/_R00T "Master _R00T") and [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan")  
     61  **Preparation:** [_R00T](/profile/_R00T "Master _R00T") and [Hamed_Ghaffari](/profile/Hamed_Ghaffari "Grandmaster Hamed_Ghaffari")
     62 
     63 **Hints**
     64 
     65 **Hint 1**
     66 
     67 The answer to the problem only depends on $x$, $n$, the index of the wall Hamid would hit if he moves to the left, and the index of the wall he would hit if he moves to the right.
     68 
     69 **Hint 2**
     70 
     71 If we denote the two indices defined in Hint 1 as $L$ and $R$, then in each of Hamid's turns, he can move in a way that ensures by the next time, either $L$ has decreased by at least one, or $R$ has increased by at least one, regardless of Mani's moves. So, if it's Hamid's turn, what is the maximum possible answer in terms of $L$, $R$, and $n$?
     72 
     73 **Answer**
     74 
     75 The answer is at most $\min(L + 1, n - R + 2)$.
     76 
     77 **Solution**
     78 
     79 Suppose it's Hamid's turn. If there is no wall to his right or to his left, he can escape the grid in one move. Otherwise, define:
     80 
     81 * $L$ as the index of the wall Hamid would reach if he moves to the left.
     82 * $R$ as the index of the wall he would reach if he moves to the right.
     83 
     84 Hamid can move to the left and decrease $L$ by at least one. (Since $L$ is always to the left of Hamid's current position, when Hamid moves left, he reaches and destroys the wall at position L. As a result, on his next turn, the new L will be at least one position further to the left. meaning $L$ decreases by at least one, regardless of Mani's actions.) Similarly, Hamid can increase $R$ by at least $1$ by moving to the right and destroying the wall there.
     85 
     86 So, since Hamid wants to escape in the minimum number of moves, he can escape the grid in at most $\min(L + 1, n - R + 2)$ moves.
     87 
     88 On the other hand, with each of Hamid's moves, Mani can place a wall in such a way that $L$ decreases by at most one or R increases by at most one.
     89 
     90 So the minimum number of moves Hamid needs is also $\min(L + 1, n - R + 2)$.
     91 
     92 Therefore, assuming Hamid starts first, the answer is $\min(L + 1, n - R + 2)$.
     93 
     94 Now consider Mani's first move. Since Mani wants to maximize the number of days Hamid needs. Moreover, with each of his moves, at least one of the $L$ or $R$ remains unchanged. So, on his first move, he can:
     95 
     96 * maximize $L + 1$ by setting $L = x - 1$, or
     97 * maximize $n - R + 2$ by minimizing $R$, setting it to $x + 1$.
     98 
     99 So the answer becomes either $\min((x-1) + 1, n - R + 2)$ or $\min(L + 1, n - (x+1) + 1)$.
    100 
    101 Because Mani wants the number of days to be as large as possible, the final answer is: $\max(\min(x, n - R + 2), \min(L + 1, n - x + 1))$
    102 
    103 We can easily find L and R with a time complexity of $\mathcal{O}(n)$. Therefore, the problem is solved in $\mathcal{O}(n)$ time complexity.
    104 
    105 **Code**
    106 
    107 ```
    108 #include<bits/stdc++.h>
    109 using namespace std;
    110 
    111 int32_t main() {
    112     cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    113     int tc;
    114     cin >> tc;
    115     while(tc--) {
    116         int n, x;
    117         string s;
    118         cin >> n >> x >> s;
    119         if(x==1 || x==n) {
    120             cout << "1\n";
    121             continue;
    122         }
    123         x--;
    124         int inf = 1e9;
    125         int lf=-inf, rg=inf;
    126         for(int i=x-1; i>=0; i--)
    127             if(s[i]=='#') {
    128                 lf=i;
    129                 break;
    130             }
    131         for(int i=x+1; i<n; i++)
    132             if(s[i]=='#') {
    133                 rg=i;
    134                 break;
    135             }
    136         if(lf==-inf && rg==inf) {
    137             cout << "1\n";
    138             continue;
    139         }
    140         cout << max(min(x+1, n-rg+1), min(lf+2, n-x)) << '\n';
    141     }
    142     return 0;
    143 }
    144 ```
    145 
    146 ---
    147 
    148 [2127C - Trip Shopping](/contest/2127/problem/C)  
    149  **Idea:** [Bahamin](/profile/Bahamin "Master Bahamin")  
    150  **Preparation:** [Bahamin](/profile/Bahamin "Master Bahamin") and [_R00T](/profile/_R00T "Master _R00T")
    151 
    152 **Hints**
    153 
    154 **Hint 1**
    155 
    156 We can see that permuting arrays $a$ and $b$ **in the same way** or changing $a_i$ with $b_i$ for a specific index $i$ doesn't change the answer. WLOG assume $a_i \leq b_i$ is always true.
    157 
    158 **Hint 2**
    159 
    160 Imagine Ali selects indices $i$ and $j$ in a round of game. What are all the different new arrays Bahamin can achieve?
    161 
    162 Can Ali ever achieve a $value$ less that the initial $value$?
    163 
    164 **Answer**
    165 
    166 He can't. Because Bahamin can always keep the chosen indices as they are, and so the $value$ won't change. No matter what Ali does.
    167 
    168 **Solution**
    169 
    170 Read the hints.
    171 
    172 Let’s first address hint $2$. To determine all arrays that Bahamin can reach, WLOG assume $a_i \leq b_i \leq a_j \leq b_j$. The specific order doesn't matter, since Bahamin can permute them freely. Set $x_1 = a_i$, $x_2 = b_i$, $x_3 = a_j$, $x_4 = b_j$ — this makes the following cases reachable for Bahamin:
    173 
    174 1. $a_i := x_1, b_i := x_2, a_j := x_3, b_j := x_4 \rightarrow \space value = x_2 - x_1 + x_4 - x_3$
    175 2. $a_i := x_1, b_i := x_3, a_j := x_2, b_j := x_4 \rightarrow \space value = x_3 - x_1 + x_4 - x_2$
    176 3. $a_i := x_1, b_i := x_4, a_j := x_2, b_j := x_3 \rightarrow \space value = x_4 - x_1 + x_3 - x_2$
    177 
    178 Other cases are similar (based on Hint $1$). We observe that the second and third options yield the same $value$, while the first option is exactly $2 \times (x_3 - x_2)$ **less** than the other two. There are now two possible cases:
    179 
    180 **Case 1:** Ali can choose two indices $i$ and $j$ such that the ordering of $[a_i, b_i, a_j, b_j]$ already matches one of the second or third options. In this case, Bahamin cannot increase the value when he is **initially** given indices $i$ and $j$. Since Ali also cannot reduce the $value$, his optimal strategy is to always give Bahamin such indices so that the final $value$ remains equal to the initial $value$.
    181 
    182 **Case 2:** Ali cannot find any two indices $i$ and $j$ that match the second or third option. This implies that for every pair of indices $i, j$, either $b_i \lt a_j$ or $b_j \lt a_i$. We claim the answer is $\sum\limits_{i=1}^{n} (b_i - a_i) + \min\limits_{1 \leq i, j \leq n, \space b_i \lt a_j} (2 \times (a_j - b_i))$.
    183 
    184 A strategy for Ali is to always select the two indices $i, j$ such that $b_i \lt a_j$ and the difference $a_j - b_i$ is minimized. Bahamin can increase the $value$ only once — when he changes the configuration of indices $i, j$ from the first option to either the second or third option. We know this increases the initial $value$ by exactly $2 \times (a_j - b_i)$. Also, it's impossible for Ali to force any $value$ lower than this. Since regardless of Ali's selection, Bahamin can always change it to the second or third option, and by definition, any choice by Ali gives Bahamin a chance to increase $value$ by **at least** our claimed amount. Also Bahamin should skip his turn (i.e., make no changes) on all subsequent turns after the first.
    185 
    186 Now to calculate the answer so that it fits the time limit, let’s first represent our array as a set of $n$ segments of the form $[a_i, b_i]$ on the number line. An interesting property of this representation is that the first option now corresponds to two completely separate intervals, while the second and third options correspond to two intersecting intervals.
    187 
    188 Now finding the answer becomes relatively easy. Sort the intervals by their left endpoint. If there are two neighboring intervals that intersect, then the input satisfies the **Case 1** condition, and so the answer is the initial $value$. Otherwise, we observe that all pairs of intervals are non-intersecting, and thus the input satisfies the **Case 2** condition. The answer, based on **Case 2** and our earlier definitions, is $2 \times (\text{distance between closest two segments}) + (\text{initial value})$.
    189 
    190 The two closest intervals must also be adjacent after sorting by their left endpoint. So, by computing the minimum distance between each pair of neighboring intervals, we obtain a solution in $\mathcal{O}(n \log n)$.
    191 
    192 **Code**
    193 
    194 ```
    195 #include <bits/stdc++.h>
    196 using namespace std;
    197 
    198 const int MXN = 2e5+5;
    199 
    200 int n, k, a[MXN];
    201 
    202 void Main() {
    203     cin >> n >> k;
    204     for(int i=1; i<=n; i++) cin >> a[i];
    205     vector<pair<int, int>> vec;
    206     long long ans = 0;
    207     for(int i=1, b; i<=n; i++) {
    208         cin >> b;
    209         if(b<a[i]) swap(b, a[i]);
    210         ans += b-a[i];
    211         vec.push_back({a[i], b});
    212     }
    213     sort(vec.begin(), vec.end());
    214     for(int i=1; i<n; i++)
    215         if(vec[i].first<=vec[i-1].second) {
    216             cout << ans << '\n';
    217             return;
    218         }
    219     int mn = 2e9;
    220     for(int i=1; i<n; i++)
    221         mn = min(mn, vec[i].first - vec[i-1].second);
    222     cout << ans + 2*mn << '\n';
    223 }
    224 
    225 int32_t main() {
    226     cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    227     int tc;
    228     cin >> tc;
    229     while(tc--) Main();
    230 }
    231 ```
    232 
    233 **Bonus**
    234 
    235 There were completely different versions of this problem at first.
    236 
    237 The original version was that Ali and Bahamin would take turns, and on each turn, a player would perform **both** operations described in the problem. Their goals and the constraints were similar to what is stated in the final version of the question.
    238 
    239 Can you solve it?
    240 
    241 ---
    242 
    243 [2127D - Root was Built by Love, Broken by Destiny](/contest/2127/problem/D)  
    244  **Idea:** [_R00T](/profile/_R00T "Master _R00T") and [Bahamin](/profile/Bahamin "Master Bahamin")  
    245  **Preparation:** [_R00T](/profile/_R00T "Master _R00T") and [Hamed_Ghaffari](/profile/Hamed_Ghaffari "Grandmaster Hamed_Ghaffari")
    246 
    247 **Hints**
    248 
    249 **Hint 1**
    250 
    251 We can prove that the map of Destinyland contains no cycles.
    252 
    253 **Hint 2**
    254 
    255 Take a look at the map below:  
    256  ![ ](/predownloaded/ec/68/ec685d26ad5bed3f4580ccbc063510078b7cec17.png)
    257 
    258 **Hint 3**
    259 
    260 Prove that a tree can be a valid Destinyland map if and only if it does **not** contain a subtree that looks like the one shown in **Hint 2**.
    261 
    262 **Hint 4**
    263 
    264 If we remove all the leaves from the Destinyland tree, the remaining graph forms a simple path.
    265 
    266 **Solution**
    267 
    268 Let $G$ be the graph of the Destinyland map.
    269 
    270 If there exists a subgraph $H$ of $G$ that cannot be a valid Destinyland map, then $G$ itself cannot be valid either.
    271 
    272 To prove this, assume, for contradiction, that $G$ is valid but $H$ is not. Then, by removing the vertices and edges not in $H$, we get a subgraph $H$ that should also be valid. But it isn't! This contradicts our assumption, so $G$ cannot be valid either.
    273 
    274 **Lemma 1:** A cycle of any length **cannot** be a valid Destinyland map.  
    275  **Proof:** Assume the opposite. Let $v$ be the leftmost house on the northern side. It has two neighbors on the southern side. Let the one on the left be $L$ and the other one $R$. Since $L$ must have another neighbor besides $v$, that neighbor cannot be on the southern side, so it must be on the northern side. However, since $v$ is the leftmost node, this neighbor must be to the right of $v$, and the edge between $L$ and this neighbor would cross the edge $v$—$L$. This contradiction shows that $L$ cannot have another neighbor besides $v$, which contradicts our assumption that the graph is a cycle.
    276 
    277 **Lemma 2:** The following tree **cannot** be a valid Destinyland map:  
    278 ![ ](/predownloaded/ec/68/ec685d26ad5bed3f4580ccbc063510078b7cec17.png)  
    279  **Proof:** Vertices $2$, $3$, and $4$ are all on the side opposite vertex $1$. If we place them in order from left to right as $u_1$, $u_2$, and $u_3$, then the neighbor of $u_2$ will necessarily create a crossing either with edge $1$—$u_1$ or $1$—$u_3$. Therefore, it is impossible to arrange the vertices of this tree in a valid Destinyland layout.  
    280   
    281   
    282  From **Lemma 1** and **Lemma 2**, we conclude that:
    283 
    284 * $G$ must be a tree.
    285 * No vertex in $G$ can be connected to three or more non-leaf neighbors.
    286 
    287 Now, remove all the leaf nodes. Since these leaves are always non-cut vertices (i.e., their removal doesn't disconnect the tree), the remaining graph, if it exists, is still connected. Since all remaining vertices have degree at most $2$. So the resulting structure must be a **path**.
    288 
    289 **Case 1:** The graph becomes empty after removing leaves.  
    290  In this case, the original graph was just a single edge. So the answer is simply $2$.
    291 
    292 **Case 2:** Only one vertex remains.  
    293  In this case, the original tree was a star. Depending on which side we place the central vertex, and how we permute the leaves, the answer is: $2\times(n−1)!$
    294 
    295 **Case 3:** Two connected non-leaf vertices $u$ and $v$ remain.  
    296  In this case, there are $4$ valid placements depending on which one is on the northern side and how their adjacent leaves are arranged around the other. ( **Note:** It's impossible for either $u$ or $v$ to have neighbors on both sides of the other.)  
    297  So the answer is: $4\times(d_u−1)!\times(d_v−1)!$ where $d_u$ and $d_v$ are the degrees of $u$ and $v$, respectively.
    298 
    299 **Case 4:** The remaining structure is a path of length at least $3$.  
    300  In this case, we have $4$ valid ways to place it. These depend on which vertices are placed on the northern side, and how the two vertices from one side with at least two vertices are positioned. (Since the path has at least $3$ vertices, there's no conflict.)
    301 
    302 Now, we only need to arrange the leaves adjacent to each vertex relative to each other. Because their positions relative to the other vertices depend only on the four ways to arrange the main path. The proof of that is boring, so we won’t bore you with it :)
    303 
    304 Let $S$ be the set of vertices on the path, and let $Saha_i$ be the number of leaves connected to vertex $i$. Then the total number of valid layouts is: $4 \times \prod\limits_{r \in S} (Saha_r!)$
    305 
    306 To implement the solution:
    307 
    308 1. Check if the input graph is a tree.
    309 2. Verify that no vertex has more than two non-leaf neighbors.
    310 3. Count the number of non-leaf vertices.
    311 4. Based on that count, determine which case applies and compute the answer accordingly.
    312 
    313 The entire algorithm runs in $\mathcal{O}(n)$ time.
    314 
    315 **Code**
    316 
    317 ```
    318 #include <bits/stdc++.h>
    319 using namespace std;
    320 
    321 #define SZ(x) int(x.size())
    322 
    323 const int  MOD    = 1e9  + 7;
    324 const int MXN    = 2e5  + 5;
    325 
    326 int n, m, fact[MXN];
    327 vector<int> adj[MXN];
    328 
    329 int32_t main() {
    330     cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    331     fact[0] = 1;
    332     for (int i = 1; i < MXN; i++) 
    333         fact[i] = (1ll * fact[i-1] * i) % MOD;
    334     int T;
    335     cin >> T;
    336     while (T--) {
    337         cin >> n >> m;
    338         for (int i = 1; i <= n; i++) adj[i].clear();
    339         for (int i = 1; i <= m; i++) {
    340             int u, v;
    341             cin >> u >> v;
    342             adj[u].push_back(v);
    343             adj[v].push_back(u);
    344         }
    345 
    346         long long ans = 2;
    347         int tl = 0;
    348         if (m >= n) ans = 0;
    349         for (int u = 1; u <= n; u++) {
    350             if (adj[u].size() > 1) {
    351                 int x = 0;
    352                 for (int v : adj[u]) {
    353                     x += (SZ(adj[v]) == 1);
    354                 }
    355                 if (x >= SZ(adj[u]) - 2) (ans *= fact[x]) %= MOD;
    356                 else ans = 0;
    357             } else tl ++;
    358         }
    359         if (tl < n-1) tl = 2; else tl = 1;
    360         cout << (ans * tl % MOD) << '\n';
    361     }
    362     return 0;
    363 }
    364 ```
    365 
    366 ---
    367 
    368 [2127E - Ancient Tree](/contest/2127/problem/E)  
    369  **Idea:** [Bahamin](/profile/Bahamin "Master Bahamin")  
    370  **Preparation:** [Bahamin](/profile/Bahamin "Master Bahamin") and [Hamed_Ghaffari](/profile/Hamed_Ghaffari "Grandmaster Hamed_Ghaffari")
    371 
    372 **Hints**
    373 
    374 **Hint 1**
    375 
    376 There are some vertices that will always be *cutie*, no matter how the other vertices are colored. What are these vertices?
    377 
    378 **Hint 2**
    379 
    380 We can show that there exists a coloring where only the vertices mentioned in **Hint 1** become *cutie*. So, the final answer is the sum of the weights of the vertices mentioned in **Hint 1**.
    381 
    382 **Solution**
    383 
    384 Read the hints.
    385 
    386 We will use a very useful and interesting technique called the **Virtual Tree** (or **Auxiliary Tree**). You can learn more here: [Virtual Tree](https://usaco.guide/plat/VT?lang=cpp). There are other solutions to this problem, but they use a similar core idea.
    387 
    388 The **virtual tree** of a set of vertices like $S$ is defined as this set:
    389 
    390 $A = S \cup \{\operatorname{lca}(u, v) \mid u, v \in S \}$
    391 
    392 Now let's build this virtual tree for the vertices of each color separately. After this, all vertices fall into three categories:
    393 
    394 1. Vertices that are in no virtual tree.
    395 2. Vertices that are in exactly one virtual tree.
    396 3. Vertices that appear in more than one virtual tree.
    397 
    398 Every vertex like $u$ of the third type will definitely be *cutie*, because no matter what color it is assigned, at least one of the colors of the virtual trees it belongs to will be different from $u$'s color.
    399 
    400 So the answer is at least the sum of the weights of all type-3 vertices.
    401 
    402 To construct an example with exactly this answer, run a $DFS$ algorithm. Every time you enter a vertex $u$, consider the following cases:
    403 
    404 * It's type 2. In that case, color it with the color of the virtual tree it belongs to.
    405 * It's type 3. In that case, color it with any color from its subtree (such a color exists by definition). This vertex is *cutie* anyway.
    406 * It's type 1 and there is some colored vertex in its subtree. Then color this vertex with that color.
    407 * It's type 1 and its entire subtree is uncolored. In that case, color this vertex with its parent's color.
    408 
    409 To prove this coloring is valid, observe that coloring a vertex $u$ with a color from its subtree does not make any new vertices *cutie* (because any such vertex would already have become *cutie* due to the same color in $u$'s subtree). Also, no vertex strictly inside $u$'s subtree changes status. And $u$ itself doesn't increase the cost based on how we chose its color.
    410 
    411 Now, for the case where we color $u$ with its parent’s color: if any new *cutie* vertex appears, it must be the parent. But since both have the same color, there’s no additional cost.
    412 
    413 Also, in this constructed example, we never introduce any new colors. So all colors stay within the range $[1, k]$.
    414 
    415 Therefore, the final answer is always the sum of the weights of **type-3 vertices**—those that appear in more than one virtual tree. These virtual trees can be constructed in $\mathcal{O}(n \log n)$.
    416 
    417 **Code**
    418 
    419 ```
    420 #include <bits/stdc++.h>
    421 using namespace std;
    422 
    423 using ll = long long;
    424 
    425 const int MXN = 2e5+1, LOG = 18;
    426 
    427 int n, k, w[MXN], c[MXN], par[LOG][MXN], stt[MXN], timer, h[MXN], cnt[MXN], col[MXN];
    428 vector<int> g[MXN], cols[MXN];
    429 bool mark[MXN], cutie[MXN];
    430 
    431 void dfs(int v) {
    432     stt[v] = timer++;
    433     for(int i=1; i<LOG; i++) par[i][v] = par[i-1][par[i-1][v]];
    434     for(int u : g[v])
    435         if(u!=par[0][v]) {
    436             h[u] = h[v]+1;
    437             par[0][u] = v;
    438             dfs(u);
    439         }
    440 }
    441 
    442 inline int jump(int v, int d) {
    443     for(int i=0; i<LOG; i++)
    444         if(d>>i&1)
    445             v = par[i][v];
    446     return v;
    447 }
    448 
    449 inline int LCA(int u, int v) {
    450     if(h[u]<h[v]) swap(u, v);
    451     u = jump(u, h[u]-h[v]);
    452     if(u==v) return u;
    453     for(int i=LOG-1; i>=0; i--)
    454         if(par[i][u]!=par[i][v])
    455             u = par[i][u], v = par[i][v];
    456     return par[0][u];
    457 }
    458 
    459 void DFS(int v, int cc) {
    460     if(c[v]) cc=c[v];
    461     else c[v]=cc;
    462     for(int u : g[v])
    463         if(u!=par[0][v])
    464             DFS(u, cc);
    465 }
    466 
    467 void Main() {
    468     cin >> n >> k;
    469     timer = 0;
    470     for(int i=1; i<=n; i++) {
    471         cnt[i] = 0;
    472         col[i] = 0;
    473         g[i].clear();
    474         cutie[i] = 0;
    475         cols[i].clear();
    476     }
    477     for(int i=1; i<=n; i++) cin >> w[i];
    478     for(int i=1; i<=n; i++) cin >> c[i], cols[c[i]].push_back(i);
    479     for(int i=1, u,v; i<n; i++) {
    480         cin >> u >> v;
    481         g[u].push_back(v);
    482         g[v].push_back(u);
    483     }
    484     bool fnd=0;
    485     for(int i=1; i<=n; i++)
    486         fnd |= c[i];
    487     if(!fnd) {
    488         cout << "0\n";
    489         for(int i=1; i<=n; i++) cout << "1 ";
    490         cout << '\n';
    491         return;
    492     }
    493     dfs(1);
    494     for(int i=1; i<=k; i++) {
    495         sort(cols[i].begin(), cols[i].end(), [&](int u, int v) {
    496             return stt[u]<stt[v];
    497         });
    498         vector<int> V;
    499         for(int j=0, u, v, lca; j+1<int(cols[i].size()); j++) {
    500             u = cols[i][j], v = cols[i][j+1], lca = LCA(u, v);
    501             if(!mark[lca]) {
    502                 if(c[lca]) {
    503                     if(c[lca] != i) cutie[lca] = 1;
    504                     continue;
    505                 }
    506                 mark[lca] = 1;
    507                 cnt[lca]++;
    508                 col[lca] = i;
    509                 V.push_back(lca);
    510             }
    511         }
    512         for(int v : V) mark[v] = 0;
    513         cols[i].clear();
    514     }
    515     ll val=0;
    516     for(int i=1; i<=n; i++) {
    517         if(cutie[i] || cnt[i]>1) val += w[i];
    518         if(!c[i] && cnt[i]==1) c[i] = col[i];
    519     }
    520     cout << val << '\n';
    521     for(int i=1; i<=n; i++)
    522         if(c[i]) {
    523             DFS(1, c[i]);
    524             break;
    525         }
    526     for(int i=1; i<=n; i++) cout << c[i] << ' ';
    527     cout << '\n';
    528 }
    529 
    530 int32_t main() {
    531     cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    532     int tc;
    533     cin >> tc;
    534     while(tc--) Main();
    535     return 0;
    536 }
    537 ```
    538 
    539 ---
    540 
    541 [2127F - Hamed and AghaBalaSar](/contest/2127/problem/F)  
    542  **Idea:** [Hamed_Ghaffari](/profile/Hamed_Ghaffari "Grandmaster Hamed_Ghaffari") and [_R00T](/profile/_R00T "Master _R00T")  
    543  **Preparation:** [Hamed_Ghaffari](/profile/Hamed_Ghaffari "Grandmaster Hamed_Ghaffari")
    544 
    545 **Hints**
    546 
    547 **Hint 1**
    548 
    549 What exactly is $f(a)$?
    550 
    551 **Answer**
    552 
    553 $f(a)$ is the sum of maximums minus the sum of element right after a maximum minus $a_1$.
    554 
    555 **Hint 2**
    556 
    557 Fix the maximum. How to count the sum of maximums?
    558 
    559 **Hint 3**
    560 
    561 You need to solve the following sub-problem:
    562 
    563 You are given three integers $n$, $m$, and $x$. How many arrays $a_1,a_2,\ldots,a_n$ exists such that:
    564 
    565 * $0 \leq a_i \leq x$ for all $1 \leq i \leq n$
    566 * $a_1 + a_2 + \ldots + a_n = m$
    567 
    568 **Hint 4**
    569 
    570 The sub-problem can be solved in $\mathcal{O}(m/x)$ using inclusion exclusion.
    571 
    572 **Hint 5**
    573 
    574 How to count the sum of an specific element in the sub-problem of **Hint 3**?
    575 
    576 **Solution**
    577 
    578 **Observation:** $f(a)$ is the sum of maximums minus the sum of element right after a maximum minus $a_1$.
    579 
    580 **Proof**
    581 
    582 Suppose that $1 = i_1 \lt i_2 \lt \ldots \lt i_k = n$ is the indices that we visit in the algorithm, and $1 \leq j_1 \lt j_2 \lt \dots \lt j_t = k$ is the indices such that $a_{i_{j_p}}$ is maximum for all $1 \leq p \leq t$.
    583 
    584 If we group the indices like below:
    585 
    586 * $i_1, \ldots, i_{j_1}$
    587 * $i_{j_1+1}, \ldots, i_{j_2}$
    588 * ...
    589 * $i_{j_{t-1}+1}, \ldots, i_k$
    590 
    591 each group will be increasing and $f(a)$ will be:
    592 
    593 $(a_{i_{j_1}}-a_{i_1}) + \ldots + (a_n - a_{i_{j_{t-1}+1}}) = \sum\limits_{p=1}^{t}a_{i_{j_p}} - \sum\limits_{p=1}^{t-1}a_{i_{j_p+1}} - a_1$
    594 
    595 Let $g(n, m, x)$ be the answer of the sub-problem in **Hint 3**. We can calculate $g(n, m, x)$ is $\mathcal{O}(m/x)$ using inclusion exclusion and "Stars and bars".
    596 
    597 $g(n, m, x) = \sum\limits_{t=0}^{\lfloor \frac{m}{x+1} \rfloor}{(-1)^t \binom{n}{t} \binom{m + n - 1 - t(x+1)}{n - 1}}$
    598 
    599 From now we fix $a_n = x$ and calculate the sum of $f(a)$ over all *snake* arrays with maximum equal to $x$.
    600 
    601 **Counting the sum of maximums:**
    602 
    603 The sum of $a_n$ over all arrays is $x \cdot g(n-1,m-x,x)$. The sum of $a_i$ for all $1 \leq i \leq n-1$ such that $a_i=x$ is $x \cdot (n-1) \cdot g(n-2, m-2x, x)$.
    604 
    605 **Counting the sum of $a_1$:**
    606 
    607 Let $s_i$ be the sum of $a_i$ over all *snake* arrays with $a_n=x$ for all $1 \leq i \lt n$.
    608 
    609 It turns out that $s_i = s_j$ for all $1 \leq i, j \lt n$, because we can swap $a_i$ and $a_j$ in every array and there is no difference between $i$ and $j$.
    610 
    611 The sum of $a_1,a_2,\ldots,a_{n-1}$ in every *snake* array is $m-x$, so $s_1+s_2+\ldots+s_{n-1} = (m-x)g(n-1,m-x,x) \rightarrow \space s_1 = \frac{m-x}{n-1}g(n-1,m-x,x).$
    612 
    613 **Counting the sum of elements right after a maximum:**
    614 
    615 This part is similar to $a_1$ part. Suppose that $a_{i-1}=x$, the sum is $(m-2x)g(n-2,m-2x,x)$ for all $1 \lt i \lt n$, and $x \cdot g(n-2, m-2x,x)$ for $i=n$.
    616 
    617 Since for each $x$ we just need $g(n-1, m-x, x)$ and $g(n-2, m-2x, x)$, the solution runs in $\sum\limits_{x=0}^{m}{\frac{m}{x+1}} = \mathcal{O}(m\log m)$.
    618 
    619 **Code**
    620 
    621 ```
    622 #include <bits/stdc++.h>
    623 using namespace std;
    624 
    625 using ll = long long;
    626 
    627 const int MXN = 4e5+5;
    628 const int MOD = 1e9+7;
    629 
    630 ll power(ll a, ll b) {
    631     ll res = 1;
    632     while(b) {
    633         if(b&1) (res *= a) %= MOD;
    634         (a *= a) %= MOD;
    635         b >>= 1;
    636     }
    637     return res;
    638 }
    639 
    640 ll F[MXN], I[MXN];
    641 
    642 void prep() {
    643     F[0] = 1;
    644     for(int i=1; i<MXN; i++) F[i] = F[i-1]*i%MOD;
    645     I[0] = I[1] = 1;
    646     for(int i=2; i<MXN; i++) I[i] = (MOD-MOD/i)*I[MOD%i]%MOD;
    647     for(int i=2; i<MXN; i++) (I[i] *= I[i-1]) %= MOD;
    648 }
    649 ll C(int n, int r) {
    650     return r<0 || r>n ? 0 : F[n]*I[r]%MOD*I[n-r]%MOD;
    651 }
    652 ll g(int n, int m, int l) {
    653     if(n==0) return m==0;
    654     ll ans = 0;
    655     for(int t=0; t<=n && t*(l+1)<=m; t++)
    656         (ans += C(n,t)*C(m+n-1-t*(l+1), n-1)%MOD*(t%2 ? MOD-1 : 1)%MOD) %= MOD;
    657     return ans;
    658 }
    659 
    660 void solve() {
    661     ll n, m, ans=0;
    662     cin >> n >> m;
    663     ll inv = power(n-1, MOD-2);
    664     for(ll x=0; x<=m; x++) {
    665         ll g1 = g(n-1, m-x, x), g2 = g(n-2, m-2*x, x);
    666         (ans += x*(g1+g2*(n-1)%MOD)) %= MOD;
    667         ll bad=0;
    668         (bad += (m-x)*g1%MOD*inv) %= MOD;
    669         (bad += x*g2) %= MOD;
    670         (bad += (m-2*x)*g2) %= MOD;
    671         (ans += MOD-bad) %= MOD;
    672     }
    673     cout << ans << '\n';
    674 }
    675 
    676 int32_t main() {
    677     cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    678     prep();
    679     int tc;
    680     cin >> tc;
    681     while(tc--) solve();
    682     return 0;
    683 }
    684 ```
    685 
    686 ---
    687 
    688 [2127G1 - Inter Active (Easy Version)](/contest/2127/problem/G1)  
    689  **Idea:** [Ali_BBN](/profile/Ali_BBN "Candidate Master Ali_BBN")  
    690  **Preparation:** [Hamed_Ghaffari](/profile/Hamed_Ghaffari "Grandmaster Hamed_Ghaffari") and [Ali_BBN](/profile/Ali_BBN "Candidate Master Ali_BBN")
    691 
    692 **Hints**
    693 
    694 **Step 0**
    695 
    696 Consider the following graph: $i\to p_i$. We will see the permutation as the graph.
    697 
    698 When asking a permutation $q$, the result is sum of whether $q^{-1}(i) \lt q^{-1}(p_i)$.
    699 
    700 **Hint 1**
    701 
    702 Why is there a condition about $k$? If we do not have $k$, can the permutation $[2, 1, 4, 3]$ be guessed out?
    703 
    704 **Hint 2.1**
    705 
    706 When we ask a permutation, what does asking the reverse of the permutation help us with?
    707 
    708 **Hint 2.2**
    709 
    710 If we ask the reverse of the permutation except the index $k$, how many times is each edge of the permutation graph counted in total?
    711 
    712 **Hint 3**
    713 
    714 How to choose $k$?
    715 
    716 **Solution**
    717 
    718 Let $x$ be a number that we have not yet fixed, and let $k = x + 1$.
    719 
    720 This partitions the array into three segments:
    721 
    722 $ \begin{aligned} A &= [1, x] \\ B &= [x + 2, n - x] \\ C &= [n - x + 1, n] \end{aligned} $
    723 
    724 This tripartition helps in controlling the query behavior.
    725 
    726 **Queries:**
    727 
    728 Say we want to find out who maps to vertex $i$, i.e., find $j$ such that $p_j = i$.
    729 
    730 Here's how:
    731 
    732 1. Construct a permutation $q$ such that $q_k = i$
    733 2. Query this permutation $→$ receive answer $a$
    734 3. Reverse all elements of $q$ **except** the position $k$
    735 4. Query the reversed permutation $→$ receive answer $b$
    736 
    737 If we consider the permutation graph of p:
    738 
    739 * Any edge not involving $i$ contributes **once** to the total count. Why?
    740 * The edge where $p_j = i$:
    741   + Will **not** be counted if $j = q_k$. This is not possible because it is guaranteed in the question that $p_i\neq i$.
    742   + Will be counted **in only one** of the two queries if $j \in q[A \cup C]$.
    743   + Will be counted **neither** if $j \in q[B]$.
    744 * The edge where $p_i = j$ will **not** be counted at all, because $i$ is at index $k$.
    745 
    746 Thus, $a + b$ is one of $[n - 2, n - 1]$ and by comparing $a + b$, we can find **which segment** $j$ (the predecessor of $i$) lies in.
    747 
    748 **Repeating the Process:**
    749 
    750 Once you know the predecessor is in a certain half, you repeat:
    751 
    752 * Repartition the candidate set into two
    753 * Choose one half to be placed in $A \cup C$, and the other in $B$ (If we had enough capacity).
    754 * Place $i$ at index $k$ again.
    755 * Do the same query + reverse trick
    756 
    757 **Choosing k:**
    758 
    759 If we set $x = \lfloor \frac{n+1}{4} \rfloor,\quad k = x + 1$, with each iteration (both in the first query and in the rest of the queries) the size of the candidate set shrinks by a factor of 2.
    760 
    761 So to find the predecessor of one number $i$, we need $2 \log (n - 1)$ queries.
    762 
    763 To find the entire permutation of $n$ elements $2 n\log (n - 1)$ queries.
    764 
    765 We stay well within the $15 \cdot n$ limit.
    766 
    767 **Code**
    768 
    769 ```
    770 #include <bits/stdc++.h>
    771 using namespace std;
    772 
    773 #define SZ(x) int(x.size())
    774 
    775 const int MXN = 1003;
    776 
    777 int n, k, p[MXN], q[MXN], cnt=0;
    778 
    779 int ask() {
    780     cout << "? ";
    781     for(int i=1; i<=n; i++) cout << q[i] << ' ';
    782     cout << endl;
    783     int r;
    784     cin >> r;
    785     return r;
    786 }
    787 
    788 void ans() {
    789     cout << "! ";
    790     for(int i=1; i<=n; i++) cout << p[i] << ' ';
    791     cout << endl;
    792 }
    793 
    794 bool mark[MXN];
    795 
    796 void build(int i, vector<int> opt, vector<int> optbad) {
    797     fill(mark+1, mark+n+1, 0);
    798     fill(q+1, q+n+1, 0);
    799     q[k] = i;
    800     mark[i] = 1;
    801     for(int j=1; j<k && !opt.empty(); j++) {
    802         mark[q[j] = opt.back()] = 1;
    803         opt.pop_back();
    804     }
    805     for(int j=n; !opt.empty(); j--) {
    806         mark[q[j] = opt.back()] = 1;
    807         opt.pop_back();
    808     }
    809     for(int j=k+1; !optbad.empty(); j++) {
    810         mark[q[j] = optbad.back()] = 1;
    811         optbad.pop_back();
    812     }
    813     for(int j=1; j<=n; j++)
    814         if(!mark[j])
    815             opt.push_back(j);
    816     for(int j=1; j<=n; j++)
    817         if(!q[j]) {
    818             q[j] = opt.back();
    819             opt.pop_back();
    820         }
    821 }
    822 
    823 void rev() {
    824     vector<int> vec;
    825     for(int i=1; i<=n; i++)
    826         if(i!=k)
    827             vec.push_back(q[i]);
    828     for(int i=1; i<=n; i++)
    829         if(i!=k) {
    830             q[i] = vec.back();
    831             vec.pop_back();
    832         }
    833 }
    834 
    835 void Main() {
    836     cin >> n;
    837     k = (n+1)/4+1;
    838     cout << k << endl;
    839     for(int i=1; i<=n; i++) {
    840         vector<int> opt;
    841         for(int j=1; j<=n; j++)
    842             if(j!=i)
    843                 opt.push_back(j);
    844         while(opt.size()>1) {
    845             int sz = SZ(opt) - min((SZ(opt)+1)/2, n-(2*k-1));
    846             build(i,
    847             vector<int>(opt.begin(), opt.begin()+sz),
    848             vector<int>(opt.begin()+sz, opt.end()));
    849             int val = ask();
    850             rev();
    851             val += ask();
    852             if(val==n-1) opt = vector<int>(opt.begin(), opt.begin()+sz);
    853             else opt = vector<int>(opt.begin()+sz, opt.end());
    854         }
    855         p[opt.back()] = i;
    856     }
    857     ans();
    858 }
    859 
    860 int32_t main() {
    861     int tc;
    862     cin >> tc;
    863     while(tc--) Main();
    864 }
    865 ```
    866 
    867 **Bonus**
    868 
    869 This way can also be implemented with $2 \log (n - 1) + \sum\limits_{x=1}^{n - 1}{2 \log x}\sim 12 \cdot n$ queries.
    870 
    871 ---
    872 
    873 [2127G2 - Inter Active (Hard Version)](/contest/2127/problem/G2)  
    874  **Solution & Analysis:** [LMydd0225](/profile/LMydd0225 "International Grandmaster LMydd0225") and [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan")  
    875  **Preparation:** [_R00T](/profile/_R00T "Master _R00T") and [Hamed_Ghaffari](/profile/Hamed_Ghaffari "Grandmaster Hamed_Ghaffari")
    876 
    877 This version used an almost completely different approach from G1. Here's the step-by-step analysis:
    878 
    879 **Analysis (Steps & Hints)**
    880 
    881 **Step 0**
    882 
    883 Consider the following graph: $i\to p_i$. We will see the permutation as the graph.
    884 
    885 When asking a permutation $q$, the result is sum of whether $q^{-1}(i) \lt q^{-1}(p_i)$.
    886 
    887 **Hint 1.1**
    888 
    889 Why is there a condition about $k$? If we do not have $k$, can the permutation $[2, 1, 4, 3]$ be guessed out?
    890 
    891 **Step 1.2**
    892 
    893 If there is a cycle of length $2$ in the permutation graph (that is, $p_i=j$ and $p_j=i$), exactly one of the two corresponding pairs to $(p_i, p_j)$ and $(p_j,p_i)$ will be counted in any query when we do not have $k$. So we have to use $k$ for cycles of length $2$. This inspires us to do casework on cycle length $=2$ or $\ge 3$.
    894 
    895 **Step 2.1**
    896 
    897 If the whole permutation graph is composed only of cycles of length $2$, can you guess out the permutation in about $\frac{1}{2}n\log n$ queries?
    898 
    899 **Hint 2.2**
    900 
    901 You need to use the property that the permutation graph is composed **only** of cycles of length $2$.
    902 
    903 **Step 2.3**
    904 
    905 Let's say you want to determine what is $p_i$. Query any permutation $q$ with $q_k=i$. If $p_i$ is among $q_1, q_2, \ldots, q_{k-1}$, the response to the query will be $\frac{n}{2}$, otherwise, $p_i$ is among $q_{k+1}, q_{k+2}, \ldots, q_n$, and the response will be $\frac{n}{2}-1$. You can verify this by yourself. Note that permutation graph is composed **only** of cycles of length $2$.
    906 
    907 Thus, we can put $k$ around $\frac{n}{2}$ and apply binary search for a single $i\to p_i$ with $\log n$ queries. Note that when we get $p_i=j$, we also get $p_j=i$. So we only need $\frac{1}{2}n\log n$ queries in total.
    908 
    909 **Step 3.1**
    910 
    911 How can we distinguish $i\to p_i$ is in which kind of cycle, length of $2$ or length $\ge 3$? Try to solve this for a single $i$ in $2\log n$ queries. Note that you do **not** need to determine $p_i$, you just need to tell whether $i\to p_i$ is in a cycle of length $2$.
    912 
    913 **Hint 3.2**
    914 
    915 If $i\to p_i$ is in a cycle of length $\ge 3$, we have $l$ and $j$ such that $l\to i\to j$ and $l\ne j$. Otherwise, $l=j$.
    916 
    917 **Hint 3.3**
    918 
    919 Consider bitmasks.
    920 
    921 **Hint 3.4**
    922 
    923 Consider cyclic shifts. Do not use $k$.
    924 
    925 **Step 3.5**
    926 
    927 Consider the following two queries ($m \lt k$):
    928 
    929 1. $[q_1, q_2, q_3, \ldots, q_m, \ldots, q_k, \ldots]$;
    930 2. $[q_m, q_1, q_2, \ldots, q_{m-1}, \ldots, q_k, \ldots]$.
    931 
    932 Only the contribution of $x\to q_m\to y$ may change: Let's say $A=\{q_1,q_2,\ldots,q_{m-1}\}$, $B=\{q_{m+1}, q_{m+2}, \ldots q_n\}$. If $x$ and $y$ are both inside $A$ or both inside $B$, responses to query **1.** and **2.** will be the same. Otherwise, answer changes by exactly $1$. If the responses are different, we can next tell whether $x_i$ is in $A$ by looking at whether the difference is $1$ or $-1$. However, if the responses are the same, we can't tell whether they are both in $A$ or both in $B$.
    933 
    934 An idea to tell whether $x=y$ is to group numbers by their bitmasks. We can use $\log n$ times such two queries to ask for each bit (let numbers with 0 on this bit in $A$, those with 1 in $B$). In the end, we will get $x\oplus y$. Then we surely get whether $x=y$.
    935 
    936 **Hint 3.6**
    937 
    938 **Step 3.5** needs $2\log n$ queries for a single element. Can you use $n\log n$ queries to solve the problem in **Step 3.5** for all elements? Note that we are doing cyclic shifts.
    939 
    940 **Step 3.7**
    941 
    942 Note that we are doing cyclic shifts. In fact, for each $i$, we just need it to appear at $q_1$ and $q_m$ respectively, without changing the set $A$. Then, for a certain set $A$, we can do cyclic shifts $|A|$ times to get all information we need. Similar for $B$. Thus, we finished the task in **Hint 3.6** in $n\log n$ queries.
    943 
    944 Since we will fix $k$ around $\frac{n}{2}$ for cycles with length $2$, we must ensure that $|A|$ and $|B|$ are around $\frac{n}{2}$. But this is not always true. Fortunately, we can resolve this issue by assigning each integer an unqiue number $c_i$, where $0\le c_i\le 2^{\lceil\log n\rceil}-1$, so that there will be exactly $\frac{n}{2}$ (or floor and ceil) 0s and 1s on each bit. We will group the indices by $c_i$ instead. Now we can put $k=\lceil\frac{n}{2}\rceil+1$.
    945 
    946 **Final Steps**
    947 
    948 Here are the final steps of this problem. First, we run the algorithm in **Step 3**. Now we get all $x_i \oplus p_i$, where $x_i\to i\to p_i$ holds.
    949 
    950 First, we will determine all $p_i$-s on cycles of length $\ge 3$. Note that we have determined all $x_i\oplus p_i$, so we only need to determine one edge for each cycle.
    951 
    952 Note that in **Step 3**, when responses to two queries are different, we can know whether $p_i$ is in $A$ or $x_i$ is in $A$. Note that we can change $m$ arbitrarily, so we can apply binary search on $m$ to get one of $p_i$ and $x_i$. That finishes the task in $\log n$ queries for each cycle. On average for each element, it is at most $\frac{1}{3}\log n$ queries.
    953 
    954 After that, we know all $p_i$-s on cycles of length $\ge 3$, and we can calculate the response to any query $[q_1, q_2,\ldots,q_n]$ easily if we don't have $k$. Similar to **Step 2**, we can determine all $p_i$-s on cycles of length $2$ in $\frac{1}{2}n\log n$ queries. On average for each element, it is $\frac{1}{2}\log n$ queries. Thus, in the worst case where the whole permutation graph consists only of cycles of length $2$, the total number of queries is $1.5\lceil\log n\rceil\cdot n$. When $n=100$, it is $10.5\cdot n$, a little larger than the limit. We can apply a trivial optimization when doing **Step 2**: do binary serach on possible indices instead of all indices. This will use a total of at most $n\log n+\sum\limits_{i=0}^{\lfloor(n-1)/2\rfloor} \log(n-1-2\cdot i)$ queries. When $n=100$, it is $986$, which fits the constraints well.
    955 
    956 **Code**
    957 
    958 ```
    959 #include <bits/stdc++.h>
    960 #define all(s) s.begin(), s.end()
    961 using namespace std;
    962 using ll = long long;
    963 using ull = unsigned long long;
    964 
    965 int T;
    966 
    967 void solve() {
    968     int n; cin >> n;
    969     const int k = (n + 1) / 2;
    970     const int M = __lg(n - 1) + 1;
    971     cout << k + 1 << endl;
    972     
    973     vector<int> p(n + 1);
    974     
    975     auto query = [&](vector<int> &q) -> int {
    976         cout << "? ";
    977         for (int i = 1; i <= n; i++) cout << q[i] << " \n"[i == n];
    978         cout.flush();
    979         int res; cin >> res;
    980         return res;
    981     };
    982     
    983     vector<int> c(n + 1), d(1 << M);
    984     auto binary_coding = [&]() {
    985         for (int i = 0, cnt = 1; cnt <= n; i++, cnt++) {
    986             c[cnt++] = i;
    987             if (cnt <= n) c[cnt] = (1 << M) - 1 - i;
    988         }
    989         for (int i = 1; i <= n; i++) d[c[i]] = i;
    990         return;
    991     };
    992     
    993     vector<int> xors(n + 1);
    994     vector<vector<int>> res1(M, vector<int>(n + 1)), res2(M, vector<int>(n + 1));
    995     vector<int> good, bad;
    996     auto getXORs = [&]() {
    997         for (int bit = 0; bit < M; bit++) {
    998             vector<int> A, B;
    999             for (int i = 1; i <= n; i++) {
   1000                 if (c[i] & (1 << bit)) B.emplace_back(i);
   1001                 else A.emplace_back(i);
   1002             }
   1003             int m = A.size(), l = B.size();
   1004             for (int i = 0; i < m; i++) {
   1005                 vector<int> q(n + 1);
   1006                 for (int j = 0; j < m; j++) q[j + 1] = A[(j + i) % m];
   1007                 for (int j = 0; j < l; j++) q[j + m + 1] = B[j];
   1008                 int res = query(q);
   1009                 res1[bit][q[1]] = res;
   1010                 res2[bit][q[m]] = res;
   1011             }
   1012             for (int i = 0; i < l; i++) {
   1013                 vector<int> q(n + 1);
   1014                 for (int j = 0; j < l; j++) q[j + 1] = B[(j + i) % l];
   1015                 for (int j = 0; j < m; j++) q[j + l + 1] = A[j];
   1016                 int res = query(q);
   1017                 res1[bit][q[1]] = res;
   1018                 res2[bit][q[l]] = res;
   1019             }
   1020             for (int i = 1; i <= n; i++) {
   1021                 if (res1[bit][i] != res2[bit][i]) xors[i] ^= (1 << bit);
   1022             }
   1023         }
   1024         for (int i = 1; i <= n; i++) {
   1025             if (xors[i] != 0) good.emplace_back(i);
   1026             else bad.emplace_back(i);
   1027         }
   1028         return;
   1029     };
   1030     auto solve3 = [&]() {
   1031         for (auto pos : good) {
   1032             if (p[pos]) continue;
   1033             int x = xors[pos], bit = __lg(x & (-x));
   1034             vector<int> A, B;
   1035             for (int i = 1; i <= n; i++) {
   1036                 if (c[i] & (1 << bit)) B.emplace_back(i);
   1037                 else A.emplace_back(i);
   1038             }
   1039             if (c[pos] & (1 << bit)) swap(A, B);
   1040             int m = A.size(), l = B.size();
   1041             int id = 0;
   1042             for (int i = 0; i < m; i++) if (A[i] == pos) id = i;
   1043             int L = 2, R = m;
   1044             vector<int> base(n + 1);
   1045             for (int j = 0; j < m; j++) base[j + 1] = A[(j + id) % m];
   1046             for (int j = 0; j < l; j++) base[j + m + 1] = B[j];
   1047             while (L < R) {
   1048                 int mid = (L + R) >> 1;
   1049                 vector<int> q(n + 1);
   1050                 for (int i = 1; i < mid; i++) q[i] = base[i + 1];
   1051                 q[mid] = base[1];
   1052                 for (int i = mid + 1; i <= n; i++) q[i] = base[i];
   1053                 int res = query(q);
   1054                 if (res != res1[bit][pos]) R = mid;
   1055                 else L = mid + 1;
   1056             }
   1057             int s = 0;
   1058             if (res2[bit][pos] > res1[bit][pos]) p[base[L]] = pos, s = base[L];
   1059             else p[pos] = base[L], s = pos;
   1060             while (!p[p[s]]) {
   1061                 int X = xors[p[s]];
   1062                 p[p[s]] = d[X ^ c[s]];
   1063                 s = p[s];
   1064             }
   1065         }
   1066     };
   1067     auto solve2 = [&]() {
   1068         for (auto pos : bad) {
   1069             if (p[pos]) continue;
   1070             auto calc = [&](vector<int> &q) {
   1071                 int val = count(all(p), 0) / 2;
   1072                 vector<int> inv(n + 1);
   1073                 for (int i = 1; i <= n; i++) inv[q[i]] = i;
   1074                 for (int i = 1; i <= n; i++) val += (inv[i] < inv[p[i]]);
   1075                 return val;
   1076             };
   1077             vector<int> cand, ok;
   1078             for (int i = 1; i <= n; i++) {
   1079                 if (i != pos && !p[i]) cand.emplace_back(i);
   1080                 if (p[i]) ok.emplace_back(i);
   1081             }
   1082             while ((int)cand.size() != 1) {
   1083                 vector<int> q = { 0 }, L, R;
   1084                 int len = ((int)cand.size() + 1) / 2;
   1085                 for (int i = 0; i < len; i++) q.emplace_back(cand[i]), L.emplace_back(cand[i]);
   1086                 for (int i = len; i < k; i++) q.emplace_back(ok[i - len]);
   1087                 q.emplace_back(pos);
   1088                 for (int i = len; i < (int)cand.size(); i++) q.emplace_back(cand[i]), R.emplace_back(cand[i]);
   1089                 for (int i = k - len; i < (int)ok.size(); i++) q.emplace_back(ok[i]);
   1090                 int res = query(q);
   1091                 res -= calc(q);
   1092                 if (res != 0) swap(L, R);
   1093                 cand = L;
   1094                 for (auto x : R) ok.emplace_back(x);
   1095             }
   1096             p[pos] = cand[0];
   1097             p[cand[0]] = pos;
   1098         }
   1099     };
   1100     
   1101     binary_coding();
   1102     getXORs();
   1103     solve3();
   1104     solve2();
   1105     
   1106     cout << "! ";
   1107     for (int i = 1; i <= n; i++) cout << p[i] << " \n"[i == n];
   1108     cout.flush();
   1109     return;
   1110 }
   1111 
   1112 int main() {
   1113     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
   1114     cin >> T;
   1115     while (T--) {
   1116         solve();
   1117     }
   1118 }
   1119 ```
   1120 
   1121 ---
   1122 
   1123 [2127H - 23 Rises Again](/contest/2127/problem/H)  
   1124  **Idea:** [sweetweasel](/profile/sweetweasel "International Master sweetweasel") and [eren__](/profile/eren__ "Grandmaster eren__")  
   1125  **Preparation:** [Hamed_Ghaffari](/profile/Hamed_Ghaffari "Grandmaster Hamed_Ghaffari") and [_R00T](/profile/_R00T "Master _R00T")
   1126 
   1127 **Hints**
   1128 
   1129 **Hint 0**
   1130 
   1131 Each connected component of a *candy graph* is either a simple path or a simple cycle.
   1132 
   1133 **Hint 1**
   1134 
   1135 Try to break the problem down into smaller parts.
   1136 
   1137 **Hint 2**
   1138 
   1139 Take a DFS tree, at most $5$ back-edges pass through each vertex.
   1140 
   1141 **Hint 3**
   1142 
   1143 Choose a vertex $v$, brute force on the back-edges that pass through $v$ and appears in the subgraph with maximum number of edges, then remove $v$ and all back-edges that pass through $v$.
   1144 
   1145 **Hint 4**
   1146 
   1147 Now we have to solve the following sub-problem for each connected component:
   1148 
   1149 You are given a simple connected graph that each vertex belongs to at most $5$ simple cycles, and an array $d_1,d_2,\ldots,d_n (0 \leq d_i \leq 2)$. What is the subgraph with maximum number of edges that degree of vertex $i$ is at most $d_i$.
   1150 
   1151 **Hint 5**
   1152 
   1153 The sub-problem can be solved in $\mathcal{O}(2^nnm)$ with dp bitmask.
   1154 
   1155 **Hint 6**
   1156 
   1157 Let $N$ be the size of the component with the maximum size after removing $v$ and back-edges that pass through $v$.
   1158 
   1159 We can solve the problem in $\mathcal{O}(2^5 2^NNm)$.
   1160 
   1161 **Hint 7**
   1162 
   1163 Choose $v$ as the centroid of the DFS tree.
   1164 
   1165 Since $N \leq n/2$ the complexity will be $\mathcal{O}(2^5 2^{n/2}nm)$.
   1166 
   1167 **Hint 8**
   1168 
   1169 Is the complexity really $\mathcal{O}(2^5 2^{n/2}nm)$?
   1170 
   1171 **Solution**
   1172 
   1173 Each connected component of a *candy graph* is either a simple path or a simple cycle.
   1174 
   1175 Take a DFS tree, at most $5$ back-edges pass through each vertex, then choose a vertex $v$, brute force on the back-edges that pass through $v$ and appears in the subgraph with maximum number of edges, then remove $v$ and all back-edges that pass through $v$.
   1176 
   1177 Let $d_i$ be the maximum degree that vertex $i$ can have. Initially $d_i=2$ for each vertex. Each back-edge $(x,y)$ that you select, reduces $d_x$ and $d_y$ by $1$. If after selecting back-edges that pass through $v$, there exists a vertex with negative $d$, skip this case. Otherwise you have to solve the sub-problem in **Hint 4** for every connected component.
   1178 
   1179 We can solve the sub-problem with the following dp bitmask:
   1180 
   1181 Let $ans_{mask}$ be the answer for $mask$, and let $dp_{mask,u,v,l1}$ be the answer for $mask$ where the last path we selected is from $u$ to $v$ and $l1 \in \text{{0, 1}}$ means that the length of the path is $1$ or not.
   1182 
   1183 Transitions:
   1184 
   1185 * Start a new path: $ans_{mask}+1 \to dp_{mask,u,v,1}$, if $(u,v)$ is an edge outside $mask$ with $d_u, d_v \geq 1$.
   1186 * Add a vertex to the last path: $dp_{mask,u,v,l1}+1 \to dp_{mask+2^w,u,w,0}$, if $w$ is a vertex outside $mask$ and adjacent to $v$, and $d_v = 2, d_w \geq 1$.
   1187 * Make the last path cycle: $dp_{mask,u,v,0}+1 \to ans_{mask}$, if there exists a $(u, v)$ edge, and $d_u = d_v = 2$.
   1188 * Skip a vertex: $ans_{mask} \to ans_{mask+2^w}$, if $w$ is a vertex outside $mask$.
   1189 
   1190 Also, you have to solve the sub-problem for each component twice, because you can choose a DFS tree edge connected to the vertex that you've deleted and it reduces $d$ of one vertex in that component.
   1191 
   1192 It can be seen that if $N$ be the size of the component with the maximum size, the complexity will be $\mathcal{O}(2^NNm)$ for a fixed set of back-edges, and $\mathcal{O}(2^52^NNm)$ in total.
   1193 
   1194 If we select $v$ as the centroid of the DFS tree $N$ will be less than or equal to $n/2$ so the complexity will be $\mathcal{O}(2^5 2^{n/2}nm)$.
   1195 
   1196 It can be proven that $m \leq 3n$ in graphs that each vertex belongs to at most $5$ simple cycles. So the complexity will be $\mathcal{O}(2^52^{n/2}n^2)$.
   1197 
   1198 **Proof**
   1199 
   1200 We prove this by induction. suppose that $m \leq 3n$ for all graphs with $n \lt N$.
   1201 
   1202 Take a DFS tree, we can prove that the degree of a leaf is at most $3$, because otherwise at least $3$ back-edges would exit that leaf and there would be at least $6$ cycles containing that leaf.
   1203 
   1204 So there always exists a vertex with degree $\leq 3$, we can remove it, $m \leq 3(N-1) + 3 = 3N$.
   1205 
   1206 **Code**
   1207 
   1208 ```
   1209 #include <bits/stdc++.h>
   1210 using namespace std;
   1211 
   1212 #define SZ(x) int(x.size())
   1213 #define maxs(a, b) (a = max(a, b))
   1214 
   1215 const int MXN = 30, MXM = MXN*(MXN-1)/2;
   1216 
   1217 int n, m, U[MXM], V[MXM];
   1218 vector<int> g[MXN];
   1219 bool tedge[MXM], have_edge[MXN][MXN];
   1220 int sz[MXN];
   1221 
   1222 void dfs1(int v) {
   1223     sz[v] = 1;
   1224     for(int i : g[v]) {
   1225         int u = v^U[i]^V[i];
   1226         if(!sz[u]) {
   1227             tedge[i] = 1;
   1228             dfs1(u);
   1229             sz[v] += sz[u];
   1230         }
   1231     }
   1232 }
   1233 
   1234 int centroid(int v, int p=-1) {
   1235     for(int i : g[v]) if(tedge[i]) {
   1236         int u = v^U[i]^V[i];
   1237         if(u!=p && sz[u]+sz[u]>n)
   1238             return centroid(u, v);
   1239     }
   1240     return v;
   1241 }
   1242 
   1243 int ID[MXN], id_counter;
   1244 vector<int> vertices[MXN];
   1245 int dp[1<<(MXN>>1)][MXN>>1][MXN>>1][2], ans_tmp[1<<(MXN>>1)], ans[2];
   1246 
   1247 void dfs_id(int v, int p=-1) {
   1248     vertices[ID[v] = id_counter].push_back(v);
   1249     for(int i : g[v]) if(tedge[i]) {
   1250         int u = v^U[i]^V[i];
   1251         if(u!=p) dfs_id(u, v);
   1252     }
   1253 }
   1254 
   1255 int deg[MXN], pos[MXN];
   1256 
   1257 int solve_(int id) {
   1258     int n = SZ(vertices[id]);
   1259     for(int msk=0; msk<(1<<n); msk++) {
   1260         ans_tmp[msk] = -1e9;
   1261         for(int i=0; i<n; i++)
   1262             for(int j=0; j<n; j++)
   1263                 for(int x : {0,1})
   1264                     dp[msk][i][j][x] = -1e9;
   1265     }
   1266     ans_tmp[0] = 0;
   1267     for(int msk=0; msk<(1<<n); msk++) {
   1268         for(int i=0; i<n; i++) if(msk>>i&1)
   1269             for(int j=0; j<n; j++) if(i!=j && (msk>>j&1)) {
   1270                 if(deg[vertices[id][j]]==2) {
   1271                     for(int eid : g[vertices[id][j]]) if(ID[U[eid]]==ID[V[eid]]) {
   1272                         int u = vertices[id][j]^U[eid]^V[eid];
   1273                         if(!(msk>>pos[u]&1) && deg[u]>=1)
   1274                             maxs(dp[msk^(1<<pos[u])][i][pos[u]][0],
   1275                             max(dp[msk][i][j][0], dp[msk][i][j][1])+1);
   1276                     }
   1277                     if(deg[vertices[id][i]]==2 && have_edge[vertices[id][i]][vertices[id][j]])
   1278                         maxs(ans_tmp[msk], dp[msk][i][j][0]+1);
   1279                 }
   1280                 maxs(ans_tmp[msk], max(dp[msk][i][j][0], dp[msk][i][j][1]));
   1281             }
   1282         for(int i=0; i<n; i++) if(!(msk>>i&1)) {
   1283             maxs(ans_tmp[msk^(1<<i)], ans_tmp[msk]);
   1284             if(deg[vertices[id][i]]>=1)
   1285                 for(int eid : g[vertices[id][i]]) if(ID[U[eid]]==ID[V[eid]]) {
   1286                     int u = vertices[id][i]^U[eid]^V[eid];
   1287                     if(deg[u]>=1 && !(msk>>pos[u]&1))
   1288                         maxs(dp[msk^(1<<i)^(1<<pos[u])][i][pos[u]][1], ans_tmp[msk]+1);
   1289                 }
   1290         }
   1291     }
   1292     return ans_tmp[(1<<n)-1];
   1293 }
   1294 
   1295 void solve(int id, int cent_neighbour) {
   1296     ans[0] = solve_(id);
   1297     if(deg[cent_neighbour]!=0) {
   1298         deg[cent_neighbour]--;
   1299         ans[1] = solve_(id);
   1300     }
   1301     else ans[1] = -1e9;
   1302 }
   1303 
   1304 void Main() {
   1305     cin >> n >> m;
   1306     for(int i=0; i<n; i++) {
   1307         g[i].clear();
   1308         vertices[i].clear();
   1309         sz[i] = 0;
   1310         for(int j=0; j<n; j++)
   1311             have_edge[i][j] = 0;
   1312     }
   1313     for(int i=0; i<m; i++) {
   1314         tedge[i] = 0;
   1315     }
   1316     for(int i=0,u,v; i<m; i++) {
   1317         cin >> u >> v;
   1318         u--, v--;
   1319         have_edge[u][v] = have_edge[v][u] = 1;
   1320         U[i] = u;
   1321         V[i] = v;
   1322         g[u].push_back(i);
   1323         g[v].push_back(i);
   1324     }
   1325     dfs1(0);
   1326     int cent = centroid(0);
   1327     
   1328     ID[cent] = 0;
   1329     id_counter = 0;
   1330     for(int i : g[cent]) if(tedge[i]) {
   1331         int u = cent^U[i]^V[i];
   1332         id_counter++;
   1333         dfs_id(u, cent);
   1334         for(int j=0; j<SZ(vertices[id_counter]); j++)
   1335             pos[vertices[id_counter][j]] = j;
   1336     }
   1337 
   1338     vector<int> be;
   1339     for(int i=0; i<m; i++)
   1340         if(!tedge[i] && (ID[U[i]]^ID[V[i]])) be.push_back(i);
   1341 
   1342     int besz = SZ(be), answer = -1e9;
   1343 
   1344     for(int msk=0; msk<(1<<besz); msk++) {
   1345         fill(deg, deg+n, 2);
   1346         for(int i=0; i<besz; i++) if(msk>>i&1)
   1347             deg[U[be[i]]]--, deg[V[be[i]]]--;
   1348         bool deg3 = 0;
   1349         for(int i=0; i<n; i++)
   1350             if(deg[i]<0) {
   1351                 deg3 = 1;
   1352                 break;
   1353             } 
   1354         if(deg3) continue;
   1355         int cur[3];
   1356         cur[0] = cur[1] = cur[2] = -1e9;
   1357         cur[deg[cent]] = __builtin_popcount(msk);
   1358         for(int i : g[cent]) if(tedge[i]) {
   1359             int u = cent^U[i]^V[i];
   1360             solve(ID[u], u);
   1361             cur[0] = max(cur[0]+ans[0], cur[1]+ans[1]+1);
   1362             cur[1] = max(cur[1]+ans[0], cur[2]+ans[1]+1);
   1363             cur[2] = cur[2]+ans[0];
   1364         }
   1365         answer = max({answer, cur[0], cur[1], cur[2]});
   1366     }
   1367     cout << answer << '\n';
   1368 }
   1369 
   1370 int32_t main() {
   1371     cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
   1372     int tc;
   1373     cin >> tc;
   1374     while(tc--) Main();
   1375     return 0;
   1376 }
   1377 ```
   1378 
   1379 **Apology**
   1380 
   1381 It turns out there are some very simple randomized solutions we hadn’t anticipated, as well as approaches using matching and even unexpected ones like backtracking. Unfortunately, these are quite hard to detect and reject without knowing beforehand.
   1382 
   1383 We sincerely apologize for this mistake. We hope you enjoyed the rest of the problems.