codeforces-scrape

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

2193.md (22150B)


      1 Source: https://codeforces.com/blog/entry/150510
      2 
      3 Thank you for participating! Special thanks to [China001](/profile/China001 "Expert China001") and [Daki-sa](/profile/Daki-sa "Expert Daki-sa") for an alternative solution to problem H.
      4 
      5 [2193A - DBMB and the Array](/contest/2193/problem/A "Codeforces Round 1076 (Div. 3)")
      6 
      7 * Idea: [KluydQ](/profile/KluydQ "Master KluydQ")
      8 * Solution + editorial: [KluydQ](/profile/KluydQ "Master KluydQ")
      9 
     10 **Hint**
     11 
     12 Each operation increases the sum by exactly $x$, regardless of the index to which the operation was applied.
     13 
     14 **Solution**
     15 
     16 Let $A$ be the initial sum of the array $a$. Each operation adds $x$ to $A$. We need to check whether $A$ can become equal to $S$. First, $S$ must not be smaller than $A$. Second, their difference must be divisible by $x$, that is, $x$ must divide $(S - A)$.
     17 
     18 **Code**
     19 
     20 ```
     21 #include <bits/stdc++.h>
     22 
     23 using namespace std;
     24 
     25 int main()
     26 {
     27 	int t;
     28 	cin >> t;
     29 
     30 	while( t -- )
     31 	{
     32 		int n, s, x;
     33 		cin >> n >> s >> x;
     34 		int a[n + 5], sum = 0;
     35 
     36 		for( int i = 1; i <= n; i ++ ) cin >> a[i], sum += a[i];
     37 
     38 		if( sum > s || (s - sum) % x != 0 ) cout << "NO\\n";
     39 		else cout << "YES\\n";
     40 	}
     41 }
     42 ```
     43 
     44 **Did you like the problem?**
     45 
     46 * Great problem
     47 * Normal problem
     48 * Bad problem
     49 * Didn’t solve
     50 
     51 [2193B - Reverse a Permutation](/contest/2193/problem/B "Codeforces Round 1076 (Div. 3)")
     52 
     53 * Idea: [KluydQ](/profile/KluydQ "Master KluydQ")
     54 * Solution + editorial: [KluydQ](/profile/KluydQ "Master KluydQ")
     55 
     56 **Hints**
     57 
     58 **Hint 1**
     59 
     60 In the optimal permutation, the first element is always equal to $n$.
     61 
     62 **Hint 2**
     63 
     64 We need to find the minimum index $i$ that can be increased using the operation. This $i$ will be the left boundary of the operation.
     65 
     66 **Solution**
     67 
     68 If $p_1 = n$, then there is no reason to change it. If $p_1 = n$ and $p_2 = n-1$, then the second element also does not need to be changed, and so on. Thus, we need to find the first index $i$ for which $p_i \neq n-i+1$ and increase it. Our goal is to make $p_i$ equal to $n-i+1$ (then the permutation will be lexicographically maximal). Find an index $j$ such that $p_j = n-i+1$ and perform the operation on $[i, j]$.
     69 
     70 **Code**
     71 
     72 ```
     73 #include <bits/stdc++.h>
     74 
     75 using namespace std;
     76 
     77 int main()
     78 {
     79 	int t;
     80 	cin >> t;
     81 
     82 	while( t -- )
     83 	{
     84 		int n;
     85 		cin >> n;
     86 
     87 		int p[n + 5], ind = 1;
     88 
     89 		for( int i = 1; i <= n; i ++ )
     90 		{
     91 			cin >> p[i];
     92 		}
     93 		while( ind <= n && p[ind] == n - ind + 1 ) ind ++;
     94 		int id = -1;
     95 
     96 		for( int i = ind; i <= n; i ++ )
     97 		{
     98 			if( p[i] == n - ind + 1 ) id = i;
     99 		}
    100 		for( int i = 1; i < ind; i ++ ) cout << p[i] << ' ';
    101 
    102 		if( id != -1 )
    103 		{
    104 			for( int i = id; i >= ind; i -- ) cout << p[i] << ' ';
    105 			for( int i = id + 1; i <= n; i ++ ) cout << p[i] << ' ';
    106 		}
    107 		cout << '\\n';
    108 	}
    109 }
    110 ```
    111 
    112 **Did you like the problem?**
    113 
    114 * Great problem
    115 * Normal problem
    116 * Bad problem
    117 * Didn’t solve
    118 
    119 [2193C - Replace and Sum](/contest/2193/problem/C "Codeforces Round 1076 (Div. 3)")
    120 
    121 * Idea: [KluydQ](/profile/KluydQ "Master KluydQ")
    122 * Solution + editorial: [KluydQ](/profile/KluydQ "Master KluydQ")
    123 
    124 **Hint**
    125 
    126 First, try to maximize all elements of $a$, and then answer the queries.
    127 
    128 **Solution**
    129 
    130 First, try to maximize all elements of $a$, and then answer the queries. Iterate $i$ from $n$ to $1$ and set $a_i$ equal to the maximum among $a_i$, $b_i$, and $a_{i+1}$. Thus, each $a_i$ reaches its maximum value. Now we can build prefix sums on array $a$ to answer each query in $O(1)$ time.
    131 
    132 **Code**
    133 
    134 ```
    135 #include <bits/stdc++.h>
    136 #define int long long
    137  
    138 using namespace std;
    139  
    140 signed main()
    141 {
    142     int t; cin >> t;
    143     
    144     while( t -- )
    145     {
    146     	int n, q; cin >> n >> q;
    147     	int a[n + 5], b[n + 5], pref[n + 5], ans = 0;
    148     	
    149     	for( int i = 1; i <= n; i ++ ) cin >> a[i];
    150     	for( int i = 1; i <= n; i ++ ) cin >> b[i];
    151 
    152 	a[n + 1] = 0;
    153 
    154 	for( int i = n; i > 0; i -- ) a[i] = max({a[i], a[i + 1], b[i]});
    155     	
    156     	pref[0] = 0;
    157     	for( int i = 1; i <= n; i ++ ) pref[i] = pref[i - 1] + a[i];
    158     	
    159     	for( int i = 1; i <= q; i ++ ){
    160     	    int L, R; cin >> L >> R;
    161     	    cout << pref[R] - pref[L - 1] << " ";
    162     	}
    163     	cout << "\n";
    164     }
    165 }
    166 ```
    167 
    168 **Did you like the problem?**
    169 
    170 * Great problem
    171 * Normal problem
    172 * Bad problem
    173 * Didn’t solve
    174 
    175 [2193D - Monster Game](/contest/2193/problem/D "Codeforces Round 1076 (Div. 3)")
    176 
    177 * Idea: [YF_YUSUF](/profile/YF_YUSUF "Expert YF_YUSUF")
    178 * Solution + editorial: [KluydQ](/profile/KluydQ "Master KluydQ")
    179 
    180 **Hints**
    181 
    182 **Hint 1**
    183 
    184 The higher the difficulty, the fewer swords can be used. The fewer swords can be used, the fewer levels can be completed.
    185 
    186 **Hint 2**
    187 
    188 If the optimal difficulty is equal to $x$, then at least one element in array $a$ equals $x$. Otherwise, we could increase $x$ without losing swords.
    189 
    190 **Solution**
    191 
    192 Sort all swords by strength in descending order. Then if the difficulty is equal to $a_i$, the number of swords that can be used equals $i$. As the difficulty decreases, the number of swords increases, and therefore the number of levels that can be completed increases. We can maintain a pointer to the number of levels and take the maximum score among all difficulties. Such a pointer-based solution works in $O(n)$ operations.
    193 
    194 **Code**
    195 
    196 ```
    197 #include <bits/stdc++.h>
    198  
    199 using namespace std;
    200 using ll = long long;
    201  
    202 const int N = 2e5 + 12;
    203  
    204 int t, n, a[N], b[N];
    205  
    206 int main()
    207 {
    208     cin >> t;
    209     
    210     while( t -- )
    211     {
    212         cin >> n;
    213         
    214         for( int i = 1; i <= n; i ++ ) cin >> a[i];
    215         for( int i = 1; i <= n; i ++ ) cin >> b[i];
    216         
    217         int h = 0, sum = 0; ll ans = 0;
    218         sort(a + 1, a + n + 1); reverse(a + 1, a + n + 1);
    219         
    220         for( int i = 1; i <= n; i ++ )
    221         {
    222             while( h < n && sum + b[h + 1] <= i ) h ++, sum += b[h];
    223             ans = max(ans, a[i] * 1ll * h);
    224         }
    225         cout << ans << '\n';
    226     }
    227 }
    228 ```
    229 
    230 **Did you like the problem?**
    231 
    232 * Great problem
    233 * Normal problem
    234 * Bad problem
    235 * Didn’t solve
    236 
    237 [2193E - Product Queries](/contest/2193/problem/E "Codeforces Round 1076 (Div. 3)")
    238 
    239 * Idea: [Wansur](/profile/Wansur "International Grandmaster Wansur")
    240 * Solution + editorial: [Wansur](/profile/Wansur "International Grandmaster Wansur")
    241 
    242 **Hint**
    243 
    244 Try a DP approach to the problem.
    245 
    246 **Solution**
    247 
    248 We will write a dynamic programming solution. $dp[x]$ is the answer for the number $x$. Initially $dp[a_i] = 1$ for all $i$ from $1$ to $n$, and all other elements of $dp$ are equal to $10^9$. Iterate $x$ from $1$ to $n$ and consider the transition:
    249 
    250 * Iterate over all divisors $y$ of $x$.
    251 * Update $dp[x]$ with $min(dp[x], dp[y] + dp[\frac{x}{y}])$.
    252 
    253 Replace all $dp[x]$ equal to $10^9$ with $-1$ and output all values of $dp$. In this solution we iterate over all numbers from $1$ to $n$ and their divisors, which totals $O(n \log n)$ operations.
    254 
    255 **Code**
    256 
    257 ```
    258 #include <bits/stdc++.h>
    259  
    260 using namespace std;
    261 const int maxn = 1'000'012;
    262  
    263 int a[maxn], dp[maxn];
    264 int n, q;
    265  
    266 void solve() {
    267     cin >> n;
    268  
    269     for(int i = 1; i <= n; i++) {
    270         dp[i] = 1e9;
    271     }
    272     for(int i = 1; i <= n;i++) {
    273         cin >> a[i];
    274         dp[a[i]] = 1;
    275     }
    276  
    277     for(int i = 1; i <= n; i++) {
    278         for(int j = i; j <= n; j += i) {
    279             dp[j] = min(dp[j], dp[i] + dp[j / i]);
    280         }
    281     }
    282  
    283     for(int i = 1; i <= n; i++) {
    284         if(dp[i] == 1e9) {
    285             dp[i] = -1;
    286         }
    287         cout << dp[i] << " \n"[i == n];
    288     }
    289 }
    290  
    291 int32_t main() {
    292     ios_base::sync_with_stdio(false);
    293     cin.tie(nullptr);
    294  
    295     int t = 1;
    296     cin >> t;
    297     while(t--) {
    298         solve();
    299     }
    300 }
    301 ```
    302 
    303 **Did you like the problem?**
    304 
    305 * Great problem
    306 * Normal problem
    307 * Bad problem
    308 * Didn’t solve
    309 
    310 [2193F - Pizza Delivery](/contest/2193/problem/F "Codeforces Round 1076 (Div. 3)") - Idea: [YF_YUSUF](/profile/YF_YUSUF "Expert YF_YUSUF"), [KluydQ](/profile/KluydQ "Master KluydQ") - Solution + editorial: [KluydQ](/profile/KluydQ "Master KluydQ")
    311 
    312 **Hints**
    313 
    314 **Hint 1**
    315 
    316 For two points $(x_i, y_i)$ and $(x_j, y_j)$, if $x_i \lt x_j$, then pizza must be delivered to point $i$ earlier than to point $j$ (because from $(x, y)$ we cannot move to $(x-1, y)$).
    317 
    318 **Hint 2**
    319 
    320 Try a DP approach to the problem.
    321 
    322 **Solution**
    323 
    324 We split the delivery points into groups with the same $x_i$. Number the groups from $0$ to $m+1$ in increasing order of $x_i$, where $m$ is the number of distinct $x_i$. Group $0$ is the starting point and group $m+1$ is the finishing point.
    325 
    326 Since we cannot move left, we must deliver pizza to all points of group $i$ before moving to group $i+1$. Let $high_i$ be the point with the maximum $y$ and $low_i$ be the point with the minimum $y$ in group $i$. Since all points in the group lie between them, the point that will be delivered last in the group will be one of these. This means that when moving from group $i$ to group $i+1$, we will go through either $high_i$ or $low_i$.
    327 
    328 Now we can write a DP for the problem. $dp[i][0]$ is the minimum time to deliver pizza to all groups from $0$ to $i$, delivering last to $high_i$, and $dp[i][1]$ is the same but delivering last to $low_i$. Initially, $dp[0][0] = 0$ and $dp[0][1] = 0$. For all other $i \gt 0$, the transitions are:
    329 
    330 * $dp[i][0] = \min(dp[i - 1][0] + dist(high_{i-1}, low_i), dp[i - 1][1] + dist(low_{i-1}, low_i)) + dist(low_i, high_i);$
    331 * $dp[i][1] = \min(dp[i - 1][0] + dist(high_{i-1}, high_i), dp[i - 1][1] + dist(low_{i-1}, high_i)) + dist(high_i, low_i);$
    332 
    333 Here $dist(a, b)$ denotes the Manhattan distance between points $a$ and $b$. Thus, sorting all points into groups takes $O(n\log n)$ operations, and computing the DP takes $O(n)$ operations.
    334 
    335 **Code**
    336 
    337 ```
    338 #include <bits/stdc++.h>
    339  
    340 #define F first
    341 #define S second
    342 #define int long long
    343  
    344 using namespace std;
    345  
    346 int t, n, ax, ay, bx, by;
    347  
    348 signed main()
    349 {
    350     cin >> t;
    351     
    352     while( t -- )
    353     {
    354         cin >> n >> ax >> ay >> bx >> by;
    355         vector <int> x(n + 5), y(n + 5), dp[2];
    356         
    357         dp[0] = dp[1] = vector <int> (n + 5, 0);
    358         map <int, int> mx, mn;
    359         
    360         mn[ax] = mx[ax] = ay;
    361         mn[bx] = mx[bx] = by;
    362         
    363         for( int i = 0; i < n; i ++ ) cin >> x[i];
    364         for( int i = 0; i < n; i ++ ) cin >> y[i];
    365         
    366         for( int i = 0; i < n; i ++ )
    367         {
    368             mx[x[i]] = max(mx[x[i]], y[i]);
    369             
    370             if(!mn.count(x[i])) mn[x[i]] = y[i];
    371             else mn[x[i]] = min(mn[x[i]], y[i]);
    372         }
    373         int lst = ax, cnt = 0;
    374         
    375         for( auto i : mx )
    376         {
    377             if( i.F == ax )
    378             {
    379                 dp[0][0] = dp[1][0] = 0;
    380                 continue;
    381             }
    382             int need = (i.F - lst) + (mx[i.F] - mn[i.F]);
    383             cnt ++;
    384             
    385             dp[0][cnt] = min(dp[0][cnt - 1] + abs(mx[i.F] - mn[lst]), dp[1][cnt - 1] + abs(mx[i.F] - mx[lst])) + need;
    386             dp[1][cnt] = min(dp[0][cnt - 1] + abs(mn[i.F] - mn[lst]), dp[1][cnt - 1] + abs(mn[i.F] - mx[lst])) + need;
    387             
    388             lst = i.F;
    389         }
    390         cout << dp[0][cnt] << '\n';
    391     }
    392 }
    393 ```
    394 
    395 **Did you like the problem?**
    396 
    397 * Great problem
    398 * Normal problem
    399 * Bad problem
    400 * Didn’t solve
    401 
    402 [2193G - Paths in a Tree](/contest/2193/problem/G "Codeforces Round 1076 (Div. 3)")
    403 
    404 * Idea: [KluydQ](/profile/KluydQ "Master KluydQ")
    405 * Solution + editorial: [Wansur](/profile/Wansur "International Grandmaster Wansur"), [KluydQ](/profile/KluydQ "Master KluydQ")
    406 
    407 **Hint**
    408 
    409 Try dividing the vertices into pairs and ask the interactor about these pairs.
    410 
    411 **Solution**
    412 
    413 First, write the numbers of all tree vertices into a sequence $p$ in DFS order. Split the elements of sequence $p$ into pairs $(p_1, p_2)$, $(p_3, p_4)$, and so on. If $n$ is odd, temporarily ignore the last element.
    414 
    415 Iterate $i$ from 1 to $\frac{n}{2}$ and make the following query to the interactor: $?$ $p_{2i-1}$ $p_{2i}$.
    416 
    417 * If these are two adjacent vertices, then when the interactor answers $1$, we will know for sure that at least one of the vertices lies on the path. In this case, with an additional query, we can find out which of the two vertices lies on the path.
    418 * Otherwise, look at the simple path between the two vertices. All pairs before this pair have been queried, so only these two vertices have not been queried on their path. Then we are back to the same situation, where one of the vertices definitely lies on the path (if the interactor answers positively).
    419 * If we find a suitable vertex, stop the process.
    420 
    421 When $n$ is odd, one vertex remains unqueried. If we did not find a vertex from the hidden path in any pair, then we can confidently say that the remaining vertex is the one that lies on the hidden path. In the end, we obtain a solution that works in exactly $\lfloor\frac{n}{2}\rfloor + 1$ queries.
    422 
    423 **Code**
    424 
    425 ```
    426 #include <bits/stdc++.h>
    427  
    428 #define sz(x) (int)(x.size())
    429 #define pb push_back
    430  
    431 using namespace std; 
    432 const int N = 2e5 + 12;
    433  
    434 int n, x, y, a, b;
    435 vector <int> L, g[N];
    436  
    437 void dfs( int v, int p = 0 )
    438 {
    439 	L.pb(v);
    440 	
    441 	for( auto to : g[v] )
    442 	{
    443 		if( to != p ) dfs(to, v);
    444 	}
    445 }
    446 int ask( int a, int b )
    447 {
    448 	cout << "? " << a << ' ' << b << endl;
    449 	int res; cin >> res; return res;
    450 }
    451 void solve()
    452 {
    453 	cin >> n;
    454 	
    455 	L.clear();
    456 	for( int i = 1; i <= n; i ++ ) g[i].clear();
    457 	
    458 	for( int i = 1; i < n; i ++ )
    459 	{
    460 		cin >> a >> b;
    461 		g[a].pb(b), g[b].pb(a);
    462 	}
    463 	dfs(1, 0);
    464 	
    465 	for( int i = 0; i < sz(L) - 1; i += 2 )
    466 	{
    467 		a = L[i], b = L[i + 1];
    468 		
    469 		if( ask(a, b) == 1 )
    470 		{
    471 			if( ask(a, a) == 1 ) cout << "! " << a << endl;
    472 			else cout << "! " << b << endl;
    473 			return;
    474 		}
    475 	}
    476 	cout << "! " << L.back() << endl;
    477 }
    478 int main()
    479 {
    480 	int t; cin >> t;
    481 	while( t -- ) solve();
    482 }
    483 ```
    484 
    485 ##
    486 
    487 **Did you like the problem?**
    488 
    489 * Great problem
    490 * Normal problem
    491 * Bad problem
    492 * Didn’t solve
    493 
    494 [2193H - Remove the Grail Tree](/contest/2193/problem/H "Codeforces Round 1076 (Div. 3)")
    495 
    496 * Idea: [Mendeke](/profile/Mendeke "Expert Mendeke")
    497 * Solution + editorial: [Wansur](/profile/Wansur "International Grandmaster Wansur"), [China001](/profile/China001 "Expert China001"), [Daki-sa](/profile/Daki-sa "Expert Daki-sa") и [KluydQ](/profile/KluydQ "Master KluydQ")
    498 
    499 **Main solution**
    500 
    501 First, take all elements modulo $2$. Now all elements are ones and zeros. It can be noticed that if we remove all $a_i$ that are equal to zero, then $S_v$ for the remaining vertices does not change. Remove all $a_i$ equal to zero whose initial $S_v$ is odd; if $S_v$ is zero, then there is no answer. Those vertices $v$ whose $S_v$ is even are removed as the ones are removed.
    502 
    503 Now we need to deal with the ones. Remove all vertices $v$ with $a_v = 0$ from the graph, leaving a forest (a graph of several disconnected trees) of ones. Solve the problem for each new tree of ones. For a tree of ones of size $n$, there is no answer when $n$ is even. When $n$ is even, the number of edges is odd, but each removal deletes one vertex and an even number of edges. Subtracting even numbers from the initial odd number of edges, we will never reach zero edges (i.e., an empty graph). Now we claim that when $n$ is odd, an answer always exists.
    504 
    505 Let us say that for a pair of adjacent vertices $(v, u)$, vertex $v$ contributes to $u$ if after removing $u$, the component containing vertex $v$ becomes even-sized. Denote $f(v)$ as the number of vertices contributing to $v$. It can be understood that we need to delete a vertex with $f(v)=0$. The components of all neighbors of such a vertex are odd-sized, and to obtain an odd $n$, we need it to have an even number of neighbors (so we can delete it from the graph uniquely). Now it is claimed that such a vertex always exists.
    506 
    507 **Proof**
    508 
    509 Consider some edge $(v, u)$ in the tree. Since $n$ is odd, either $v$ contributes to $u$ or $u$ contributes to $v$. Therefore, the sum of all $f(v)$ equals $n-1$, and by the pigeonhole principle there exists a vertex with $f(v)=0$, which is what we needed to prove.
    510 
    511 It can be noticed that after deleting vertex $v$, values of $f$ change only for neighbors of $v$. For all neighbors $u$ of vertex $v$, the value $f(u)$ decreases by $1$, because the contribution was from $v$ to $u$. We compute all values of $f$ once, and using BFS we delete vertices with $f=0$. We also should not forget that some zeros need to be deleted as ones are removed. This solution runs in $O(n)$ operations.
    512 
    513 **Second solution**
    514 
    515 Let us say that the root of the tree is vertex $1$. We will write a DP for the problem. Define it as follows:
    516 
    517 * $dp_v = 0$ if vertex $v$ cannot be deleted.
    518 * $dp_v = 1$ if to delete vertex $v$, its parent must necessarily be deleted before $v$.
    519 * $dp_v = 2$ if to delete vertex $v$, vertex $v$ must necessarily be deleted before its parent.
    520 * $dp_v = 3$ if for deleting vertex $v$ it does not matter whether we delete the parent or the vertex first.
    521 
    522 If for at least one vertex $v$, $dp_v = 0$, then there is no answer. Let $p_v$ be the parent of vertex $v$, and let $s_v$ be the sum of all values $a_u$ where $u$ is a child of $v$ and $dp_u$ equals $1$ or $3$. For $dp_v$ to be $1$, at least one of the following conditions must hold:
    523 
    524 * The parity of $s_v$ is not equal to $a_v$.
    525 * The parity of $s_v$ equals $a_v$, but the vertex has a child $u$ with $dp_u = 3$ and $a_u = 1$. That is, we can delete $u$ before $v$, thereby changing the parity of $s_v$.
    526 
    527 Add $a_{p_v}$ to $s_v$ and check the conditions again for $dp_v = 2$. If both cases satisfy the conditions, then $dp_v = 3$, and if none of them does, then $dp_v = 0$. It remains only to restore the answer from the DP; details can be found in the implementation. The time complexity of the solution is $O(n)$.
    528 
    529 **Code for main solution**
    530 
    531 ```
    532 #include <bits/stdc++.h>
    533 #define ent '\n'
    534 #define int long long
    535  
    536 using namespace std;
    537 const int maxn = 200012;
    538 const int mod = 1e9 + 7;
    539  
    540 int cnt[maxn], a[maxn], del[maxn];
    541 int sz[maxn], bad[maxn], used[maxn];
    542 vector<int> g[maxn], e[maxn], g2[maxn];
    543 int n, m;
    544  
    545 void dfs(int v, int p) {
    546     sz[v] = 1;
    547     used[v] = true;
    548     for(int to : g[v]) {
    549         if(to == p) {
    550             continue;
    551         }
    552  
    553         dfs(to, v);
    554  
    555         if(sz[to] % 2 == 0) {
    556             e[to].push_back(v);
    557             bad[v]++;
    558         }
    559         else {
    560             e[v].push_back(to);
    561             bad[to]++;
    562         }
    563  
    564         sz[v] += sz[to];
    565     }
    566 }
    567  
    568 void solve() {
    569     cin >> n;
    570     for(int i = 1; i <= n; i++) {
    571         cin >> a[i];
    572         a[i] %= 2;
    573         del[i] = cnt[i] = sz[i] = 0;
    574         bad[i] = used[i] = 0;
    575         g[i].clear();
    576         g2[i].clear();
    577         e[i].clear();
    578     }
    579  
    580     for(int i = 1; i < n; i++) {
    581         int u, v;
    582         cin >> u >> v;
    583  
    584         cnt[u] += a[v], cnt[v] += a[u];
    585  
    586         if(a[u] && a[v]) {
    587             g[u].push_back(v);
    588             g[v].push_back(u);
    589         }
    590         if( a[u] && !a[v] ) g2[u].push_back(v);
    591         if( a[v] && !a[u] ) g2[v].push_back(u);
    592     }
    593     queue <int> q;
    594  
    595     for(int i = 1; i <= n; i++) {
    596         if(!cnt[i] && !a[i]) {
    597             cout << "NO\n";
    598             return;
    599         }
    600     }
    601     for(int i = 1; i <= n; i++) {
    602         if(a[i] && !used[i]) {
    603             dfs(i, 0);
    604             if(sz[i] % 2 == 0) {
    605                 cout << "NO\n";
    606                 return;
    607             }
    608         }
    609     }
    610     for(int i = 1; i <= n; i++) {
    611         if(a[i] && !bad[i]) {
    612             q.push(i);
    613         }
    614     }
    615     cout << "YES\n";
    616     int zero[n + 5];
    617     
    618     for( int i = 1; i <= n; i ++ ){
    619         zero[i] = 0;
    620         
    621         if( !a[i] && cnt[i] % 2 ) cout << i << ' ';
    622         else if( !a[i] ) zero[i] = 1;
    623     }
    624     while(!q.empty()) {
    625         int v = q.front(); q.pop();
    626         cout << v << ' ';
    627         for(int to : g2[v]){
    628             if(zero[to]) cout << to << ' ', zero[to] = 0;
    629         }
    630         for(int to : e[v]) {
    631             bad[to]--;
    632             if(bad[to] == 0) q.push(to);
    633         }
    634     }
    635     cout << ent;
    636 }
    637  
    638 int32_t main() {
    639     ios_base::sync_with_stdio(false);
    640     cin.tie(nullptr);
    641  
    642     int t = 1;
    643     cin >> t;
    644     while(t--) {
    645         solve();
    646     }
    647 }
    648 ```
    649 
    650 **Code for second solution**
    651 
    652 ```
    653 #include <bits/stdc++.h>
    654 
    655 using namespace std;
    656 
    657 const int N = 2e5 + 12;
    658 const int inf = 1e9 + 1;
    659 
    660 int n, x, y, a[N], dp[N], cnt[N], par[N];
    661 vector <int> g[N], g2[N]; bool flag, used[N];
    662 pair <int, int> must[N][3]; vector <int> ord;
    663 
    664 void dfs( int v, int p = 0 )
    665 {
    666 	int s = 0, ok = 0, id = 0;
    667 	par[v] = p; ord.push_back(v);
    668 	
    669 	for( auto to : g[v] )
    670 	{
    671 		if( to == p ) continue;
    672 		
    673 		dfs(to, v);
    674 		if(!flag) return;
    675 		
    676 		if( dp[to] == 1 || dp[to] == 3 )
    677 		{
    678 			s ^= a[to];
    679 			
    680 			if( dp[to] == 3 && a[to] == 1 )
    681 			{
    682 				if( !ok )
    683 				{
    684 					ok = 1;
    685 					id = to;
    686 				}
    687 			}
    688 			if( dp[to] == 3 && id != to ) dp[to] = 1;
    689 		}
    690 	}
    691 	if( !ok && s == a[v] && (s + a[p]) % 2 == a[v] )
    692 	{
    693 		flag = 0;
    694 		return;
    695 	}
    696 	if( s != a[v] || ok )
    697 	{
    698 		if( s == a[v] ) must[v][1] = {id, 2};
    699 		else if(ok) must[v][1] = {id, 1};
    700 		
    701 		dp[v] = 1;
    702 	}
    703 	s = (s + a[p]) % 2;
    704 	
    705 	if( s != a[v] || ok )
    706 	{
    707 		if( s == a[v] ) must[v][2] = {id, 2};
    708 		else if(ok) must[v][2] = {id, 1};
    709 		
    710 		dp[v] += 2;
    711 	}
    712 }
    713 void dfs2( int v, int tp )
    714 {
    715 	dp[v] = tp, used[v] = 1;
    716 	pair <int, int> p = must[v][tp];
    717 	if( p.first != 0 ) dfs2(p.first, p.second);
    718 }
    719 void solve()
    720 {
    721 	cin >> n;
    722 	flag = 1;
    723 	
    724 	// dp[v] = 1, if p[v] before v
    725 	// dp[v] = 2, if v before p[v]
    726 	
    727 	for( int i = 1; i <= n; i ++ )
    728 	{
    729 		cin >> a[i];
    730 		a[i] %= 2;
    731 		
    732 		must[i][1] = must[i][2] = {0, 0};
    733 		dp[i] = cnt[i] = used[i] = 0;
    734 		g[i].clear(), g2[i].clear();
    735 	}
    736 	for( int i = 1; i < n; i ++ )
    737 	{
    738 		cin >> x >> y;
    739 		
    740 		g[x].push_back(y);
    741 		g[y].push_back(x);
    742 	}
    743 	ord.clear();
    744 	dfs(1);
    745 	
    746 	if( !flag )
    747 	{
    748 		cout << "No\n";
    749 		return;
    750 	}
    751 	cout << "Yes\n";
    752 	
    753 	for( auto i : ord )
    754 	{
    755 		if( !used[i] )
    756 		{
    757 			if( dp[i] == 3 ) dfs2(i, 1);
    758 			else dfs2(i, dp[i]);
    759 		}
    760 	}
    761 	for( int v = 2; v <= n; v ++ )
    762 	{
    763 		if( dp[v] == 1 ) cnt[v] ++, g2[par[v]].push_back(v);
    764 		else cnt[par[v]] ++, g2[v].push_back(par[v]);
    765 	}
    766 	queue <int> q;
    767 	
    768 	for( int i = 1; i <= n; i ++ )
    769 	{
    770 		if( cnt[i] == 0 ) q.push(i);
    771 	}
    772 	while( !q.empty() )
    773 	{
    774 		int v = q.front();
    775 		q.pop(); cout << v << ' ';
    776 		
    777 		for( auto to : g2[v] )
    778 		{
    779 			cnt[to] --;
    780 			if( !cnt[to] ) q.push(to);
    781 		}
    782 	}
    783 	cout << '\n';
    784 }
    785 int main()
    786 {
    787 	ios_base::sync_with_stdio(0);
    788 	
    789 	int t; cin >> t;
    790 	while(t --) solve();
    791 }
    792 ```
    793 
    794 **Did you like the problem?**
    795 
    796 * Great problem
    797 * Normal problem
    798 * Bad problem
    799 * Didn’t solve