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