2227.md (25326B)
1 Source: https://codeforces.com/blog/entry/153099 2 3 Thanks for participating in the contest. I hope you enjoyed the problems :) 4 5 **Rating Predictions** 6 7 | Predictor | A | B | C | D | E | F | G | H | 8 | --- | --- | --- | --- | --- | --- | --- | --- | --- | 9 | [Argentum47](/profile/Argentum47 "Candidate Master Argentum47") | 800 | 800 | 900 | 1200 | 1500 | 1700 | 1900 | 2200 | 10 | [simplelife](/profile/simplelife "Specialist simplelife") | 800 | 800 | 1000 | 1300 | 1500 | 1800 | 1800 | — | 11 | [lina_os](/profile/lina_os "Pupil lina_os") | 800 | 800 | 1000 | 1100 | 1400 | — | — | — | 12 | [-firefly-](/profile/-firefly- "International Master -firefly-") | 800 | 800 | 900 | 1400 | 1600 | 1900 | 2000 | 2300 | 13 | [Syrianooo](/profile/Syrianooo "Pupil Syrianooo") | 800 | 800 | 900 | 1200 | 1300 | — | — | — | 14 | [Mousa](/profile/Mousa "Expert Mousa") | 800 | 800 | 1000 | 1300 | 1600 | 2000 | 2300 | 2100 | 15 | [yse](/profile/yse "Candidate Master yse") | 800 | 800 | 1000 | 1200 | 1400 | 1600 | 1900 | 2100 | 16 17 **Rate the contest!** 18 19 * Excellent contest 20 * Good contest 21 * Average contest 22 * Bad contest 23 * Horrible contest 24 25 **Rate the difficulty!** 26 27 * Easy contest 28 * Normal contest 29 * Hard contest 30 31 #### [A — Koshary](https://codeforces.com/contest/2227/problem/A) 32 33 **Hint** 34 35 Without short steps, we can only visit coordinates where $x$ and $y$ are both even. 36 37 **Solution** 38 39 Using only long steps, we can only visit coordinates where $x \equiv 0 \pmod 2$ and $y \equiv 0 \pmod 2$. The extra short step allows us to change either $x$ or $y$ to become odd (i.e. $x \equiv 1 \pmod 2$ or $y \equiv 1 \pmod 2$), but not both. 40 41 Thus, we can say that all coordinates are reachable except for ones where both $x$ and $y$ are odd, since that would require more than one short step. 42 43 **Code (C++)** 44 45 ``` 46 #include <bits/stdc++.h> 47 using namespace std; 48 49 int main() { 50 int t; 51 cin >> t; 52 while(t--) { 53 int x, y; 54 cin >> x >> y; 55 cout << (x % 2 == 0 || y % 2 == 0 ? "YES" : "NO") << endl; 56 } 57 } 58 ``` 59 60 **Rate the problem!** 61 62 * Excellent problem 63 * Good problem 64 * Average problem 65 * Bad problem 66 * Horrible problem 67 68 #### [B — Party Monster](https://codeforces.com/contest/2227/problem/B) 69 70 **Hint** 71 72 It can never be harmful to choose the entire string as the substring. 73 74 **Solution** 75 76 As mentioned in the hint, choosing the entire string to be the substring, that we perform the operation on, is always optimal. Let's assume a smaller substring yields a valid RBS, we can just choose the entire string, and only move around the characters which are in the smaller substring. Thus, choosing the entire string is always optimal. 77 78 Now, the problem reduces to checking if we can rearrange a bracket sequence to become an RBS. We want each '$\texttt{(}$' to pair with a '$\texttt{)}$', leaving no unpaired brackets. This is equivalent to checking whether the number of occurrences of '$\texttt{(}$' is equal to the number of occurrences of '$\texttt{)}$' in the string. 79 80 **Code (C++)** 81 82 ``` 83 #include <bits/stdc++.h> 84 using namespace std; 85 86 int main() { 87 int t; 88 cin >> t; 89 while(t--) { 90 int n; 91 cin >> n; 92 string s; 93 cin >> s; 94 95 int cnt = 0; 96 for(int i = 0; i < n; i++) cnt += s[i] == '('; 97 98 cout << (2 * cnt == n ? "YES" : "NO") << endl; 99 } 100 } 101 ``` 102 103 **Rate the problem!** 104 105 * Excellent problem 106 * Good problem 107 * Average problem 108 * Bad problem 109 * Horrible problem 110 111 #### [C — Snowfall](https://codeforces.com/contest/2227/problem/C) 112 113 **Hint 1** 114 115 A subarray should have both $2$ and $3$ as prime factors of the product to be divisible by $6$. Each element can either contribute $2$, or $3$, or both. 116 117 **Hint 2** 118 119 From the previous hint, we can split the elements into $4$ groups. 120 121 **Solution** 122 123 A subarray has product divisible by $6$ if it contains both $2$ and $3$ as prime factors. Therefore, every element falls into one of $4$ groups: 124 125 * $S_6$: Elements divisible by $6$ 126 * $S_2$: Elements divisible by $2$ but not $3$ 127 * $S_3$: Elements divisible by $3$ but not $2$ 128 * $S_1$: Elements neither divisible by $2$ nor $3$ 129 130 Elements in $S_6$ already make any subarray divisible by $6$, so we want them packed together at an end to minimize the number of subarrays they are included in. For the next 2 paragraphs, let's forget about $S_6$. 131 132 For the remaining elements, if we place all $S_2$ before all $S_3$, then the only divisible subarrays are the ones that start in $S_2$ and end in $S_3$. Any other order would only create more such subarrays. 133 134 What do we do with elements of $S_1$? Inserting them anywhere can never decrease the number of divisible subarrays, but we can avoid increasing by placing them between $S_2$ and $S_3$. Subarrays divisible by $6$ would still be ones that start in $S_2$ and end in $S_3$, so the number of divisible subarrays is still as minimal as possible. 135 136 Therefore, an optimal construction is: 137 138 $[S_6] + [S_2] + [S_1] + [S_3]$ 139 140 **Code (C++)** 141 142 ``` 143 #include <bits/stdc++.h> 144 using namespace std; 145 146 int main() { 147 int t; 148 cin >> t; 149 while(t--) { 150 int n; 151 cin >> n; 152 vector<int> a, b, c, d; 153 for(int i = 0; i < n; i++) { 154 int x; 155 cin >> x; 156 if(x % 6 == 0) a.push_back(x); 157 else if(x % 2 == 0) b.push_back(x); 158 else if(x % 3 == 0) c.push_back(x); 159 else d.push_back(x); 160 } 161 162 vector<int> ans; 163 for(auto it : a) ans.push_back(it); 164 for(auto it : b) ans.push_back(it); 165 for(auto it : d) ans.push_back(it); 166 for(auto it : c) ans.push_back(it); 167 168 for(int i = 0; i < n; i++) cout << ans[i] << " \n"[i == n - 1]; 169 } 170 } 171 ``` 172 173 **Rate the problem!** 174 175 * Excellent problem 176 * Good problem 177 * Average problem 178 * Bad problem 179 * Horrible problem 180 181 #### [D — Palindromex](https://codeforces.com/contest/2227/problem/D) 182 183 **Hint 1** 184 185 The minimum answer is $1$, because a $0$ always exists, and we can take a $0$ individually as a palindromic subarray with $\operatorname{mex} = 1$. 186 187 **Hint 2** 188 189 Any valid subarray with a $\operatorname{mex} \gt 1$ will still contain at least one $0$. So we know the optimal subarray will always contain a $0$. 190 191 **Solution** 192 193 There are several valid approaches to this problem. Here, I will explain the intended approach. 194 195 We can claim that the optimal subarray will always contain the element $0$. This is because, if it did not contain $0$, then $\operatorname{mex} = 0$. But $\operatorname{mex} = 1$ can be achieved by considering a $0$ element as its own subarray (it is palindromic). So, the optimal subarray must always contain the element $0$. 196 197 This gives us only $3$ candidate centers to expand the palindrome from. Let $x$ be the position of the first $0$ in the array, and $y$ be the position of the second $0$: 198 199 * $x$ can be the center of the optimal palindrome. 200 * $y$ can be the center of the optimal palindrome. 201 * $x$ and $y$ can be on opposite corresponding sides of the palindrome. For instance, $[\dots, 0, \dots, j, k, j, \dots, 0, \dots]$ for odd palindromes, $[\dots, 0, \dots, j, k, k, j, \dots, 0, \dots]$ for even palindromes. 202 203 We can try each of these choices, and expand from the candidate center as long as the subarray is still palindromic, while keeping track of $\operatorname{mex}$. The answer is the maximum $\operatorname{mex}$ among all $3$ candidates. 204 205 **Code (C++)** 206 207 ``` 208 #include <bits/stdc++.h> 209 using namespace std; 210 211 int n; 212 vector<int> v; 213 214 int solve(int l, int r) { 215 set<int> s; 216 for(int i = 0; i <= n; i++) s.insert(i); 217 218 while(l >= 0 && r < 2 * n && v[l] == v[r]) { 219 s.erase(v[l]); 220 l--, r++; 221 } 222 223 return *s.begin(); 224 } 225 226 int main() { 227 int t; 228 cin >> t; 229 while(t--) { 230 cin >> n; 231 v = vector<int> (2 * n); 232 for(auto &it : v) cin >> it; 233 234 int x = -1, y; 235 for(int i = 0; i < 2 * n; i++) { 236 if(!v[i]) { 237 if(~x) y = i; 238 else x = i; 239 } 240 } 241 242 cout << max({solve(x, x), solve(y, y), solve((x + y) / 2, (x + y + 1) / 2)}) << endl; 243 } 244 } 245 ``` 246 247 **Bonus** 248 249 Instead of only expanding from the $3$ possible candidates, we can brute force over all centers (even and odd palindrome centers) and only expand as long as the subarray will stay palindromic. Can you prove why this fits the time limit? 250 251 **Rate the problem!** 252 253 * Excellent problem 254 * Good problem 255 * Average problem 256 * Bad problem 257 * Horrible problem 258 259 #### [E — It All Went Sideways](https://codeforces.com/contest/2227/problem/E) 260 261 **Hint 1** 262 263 Look at one height at a time. A cube stays only if every column to its right is tall enough for that height. 264 265 **Hint 2** 266 267 The number of cubes that stay in column $i$ is exactly the suffix minimum $s_i$. 268 269 **Solution** 270 271 Let $s_i = \min(a_i, a_{i+1}, \dots, a_n)$ be the suffix minimum of the array. 272 273 The key observation is that a cube at position $(i, h)$ stays in the same column after the gravity shift if every column to its right also has a cube on height $h$. In other words, the row $h$ is already a suffix of occupied cells. This happens exactly when $h = s_i$. 274 275 So, column $i$ contributes exactly $s_i$ cubes that do not move, and therefore it contributes $a_i - s_i$ cubes that do move. Without any operation, the total number of moving cubes is $\sum_{i=1}^{n} (a_i - s_i)$. Now we try the operation. If $a_i \gt s_i$, then this decrease does not change any suffix minimum at all, because there is already a smaller somewhere to the right. Such a choice is useless. The only useful positions are those where $a_i = s_i$, which are exactly the positions where the suffix minimum array changes (i.e., $s_i \neq s_{i+1}$). 276 277 Since suffix minima are non-decreasing from left to right, equal values form contiguous blocks. If we decrease the rightmost element of such a block, then the suffix minimum on the whole block drops by $1$. This means the number of cubes that stay in place decreases by the length of that block, while the total number of cubes decreases by only $1$. Consequently, the number of moving cubes increases by $\text{block length} - 1$. 278 279 Therefore, the best strategy is to pick the longest block of equal values in the suffix minimum array. The final formula for the maximum number of moving cubes is: 280 281 $\sum_{i=1}^{n} a_i - \sum_{i=1}^{n} s_i + (\text{maximum block length in } s) - 1$ 282 283 **Code (C++)** 284 285 ``` 286 #include <bits/stdc++.h> 287 using namespace std; 288 #define ll long long 289 290 int main() { 291 int t; 292 cin >> t; 293 while(t--) { 294 int n; 295 cin >> n; 296 vector<ll> v(n); 297 ll sum = 0; 298 for(auto &it : v) { 299 cin >> it; 300 sum += it; 301 } 302 303 vector<ll> suf_mn(n); 304 suf_mn[n - 1] = v[n - 1]; 305 sum -= suf_mn[n - 1]; 306 for(int i = n - 2; i >= 0; i--) { 307 suf_mn[i] = min(suf_mn[i + 1], v[i]); 308 sum -= suf_mn[i]; 309 } 310 311 ll mx = -1, cur = 1; 312 for(int i = 1; i < n; i++) { 313 if(suf_mn[i] == suf_mn[i - 1]) cur++; 314 else { 315 mx = max(mx, cur); 316 cur = 1; 317 } 318 } 319 320 mx = max(mx, cur); 321 cout << sum + mx - 1 << endl; 322 } 323 } 324 ``` 325 326 **Rate the problem!** 327 328 * Excellent problem 329 * Good problem 330 * Average problem 331 * Bad problem 332 * Horrible problem 333 334 #### [F — It Just Keeps Going Sideways](https://codeforces.com/contest/2227/problem/F) 335 336 Thanks to [chromate00](/profile/chromate00 "Expert chromate00") for suggesting a modification to problem E, which resulted in this problem. 337 338 **Hint 1** 339 340 Cubes on the same height never interact with other heights. 341 342 **Hint 2** 343 344 For a fixed height $h$, the cubes end up in the rightmost $\texttt{cnt}[h]$ columns, where $\texttt{cnt}[h]$ is the number of cubes at height $h$. 345 346 **Hint 3** 347 348 After decreasing one column by $1$, only one height level changes, so the gain value is easy to calculate locally. 349 350 **Solution** 351 352 Fix some height $h$. A cube at height $h$ exists in column $i$ exactly when $a_i \ge h$. When gravity shifts to the right, all cubes on the same height behave independently from the other heights, they just slide as far right as possible without overlapping. Therefore, on height $h$, all cubes occupy the rightmost $\texttt{cnt}[h]$ columns, where $\texttt{cnt}[h]$ is the number of columns with $a_i \ge h$. So the whole problem can be reduced to counting, for each height, how many cubes start there and where they end up. 353 354 Let 355 356 $\texttt{cnt}[h] = \# \{i \mid a_i \ge h\}$ 357 358 Then the sum of final column indices of the cubes on height $h$ is simply the sum of an arithmetic progression: 359 360 $(n - \texttt{cnt}[h] + 1) + (n - \texttt{cnt}[h] + 2) + \dots + n = \frac{\texttt{cnt}[h](2n - \texttt{cnt}[h] + 1)}{2}$ 361 362 The sum of initial column indices of the cubes on height $h$ is the sum of all indices $i$ such that $a_i \ge h$. If we sum this over all heights, we get the total movement distance of all cubes. An easy way to compute the initial sum is column-wise instead of height-wise. A cube in column $i$ contributes $i$ to the initial column-sum for every height from $1$ to $a_i$. So the total initial sum is $\sum_{i=1}^n i \cdot a_i$. For the final sum, we use the $\texttt{cnt}[h]$ values above. So if no operation is performed, the answer is $\text{final} - \text{initial}$. 363 364 Now consider the allowed operation. Suppose $a_i = x$, then the initial sum decreases by exactly $i$, because one cube from column $i$ disappears. What happens to the final sum? Only height $x$ changes, because the column still contributes to all heights $1, 2, \dots, x-1$, but no longer contributes to height $x$. So $\texttt{cnt}[x]$ decreases by $1$, and all other heights stay unchanged. 365 366 For height $x$, the final sum of occupied columns changes from the rightmost $\texttt{cnt}[x]$ columns to the rightmost $\texttt{cnt}[x]-1$ columns. The difference is exactly $n - \texttt{cnt}[x] + 1$. So the total gain from decreasing $a_i$ is: 367 368 $i - (n - \texttt{cnt}[a_i] + 1) = i - n + \texttt{cnt}[a_i] - 1$ 369 370 That means we should compute this value for every index $i$ and take the maximum. 371 372 **Code (C++)** 373 374 ``` 375 #include <bits/stdc++.h> 376 using namespace std; 377 #define int long long 378 379 signed main() { 380 int t; 381 cin >> t; 382 while(t--) { 383 int n; 384 cin >> n; 385 vector<int> v(n + 1), cnt(n + 1); 386 for(int i = 1; i <= n; i++) { 387 cin >> v[i]; 388 cnt[v[i]]++; 389 } 390 391 vector<int> have(n + 1); 392 have[n] = cnt[n]; 393 for(int i = n - 1; i >= 1; i--) have[i] = have[i + 1] + cnt[i]; 394 395 int init = 0, aft = 0; 396 for(int i = 1; i <= n; i++) { 397 init += i * v[i]; 398 aft += have[i] * (2 * n - have[i] + 1) / 2; 399 } 400 401 int cur = aft - init, mx = 0; 402 for(int i = 1; i <= n; i++) mx = max(mx, i - n + have[v[i]] - 1); 403 404 cout << cur + mx << endl; 405 } 406 } 407 ``` 408 409 **Rate the problem!** 410 411 * Excellent problem 412 * Good problem 413 * Average problem 414 * Bad problem 415 * Horrible problem 416 417 #### [G — Drowning](https://codeforces.com/contest/2227/problem/G) 418 419 **Hint 1** 420 421 The length of the array decreases by $2$ after each operation, so only odd-length subarrays are possibly good. 422 423 **Hint 2** 424 425 Think about alternating sum. What can you notice about it after applying some operations? 426 427 **Hint 3** 428 429 Alternating sum is invariant. A good subarray must be a positive single element at the end, so the alternating sum must be positive. Is this a sufficient condition? 430 431 **Solution** 432 433 Let's define: 434 435 $S(c) = c_1 - c_2 + c_3 - c_4 + \dots + (-1)^{|c|-1}c_{|c|}$ 436 437 which is the alternating sum of an array $c$. 438 439 First, every operation keeps the parity of the length unchanged, because the length only decreases by $2$. Therefore, if an array can be reduced to length $1$, then its length must be odd. 440 441 Now, let's look at the operation. Suppose we choose an index $i$ and perform the replacement: 442 443 $(c_{i-1}, c_i, c_{i+1}) \to x = c_{i-1} - c_i + c_{i+1}$ 444 445 In the alternating sum $S(c)$, the signs of these three positions are either $(+, -, +)$ or $(-, +, -)$, depending on the parity of $i-1$. Their contribution to the total sum is: 446 447 $\pm c_{i-1} \mp c_i \pm c_{i+1} = \pm(c_{i-1} - c_i + c_{i+1}) = \pm x$ 448 449 This is exactly the contribution of the new element $x$ at that position. Therefore, the alternating sum is invariant under the operation. 450 451 Since the final array has length $1$, its alternating sum is just that single remaining number, which is positive. Therefore, every good array must have positive alternating sum. So far we have proved a necessary condition: a good array must have odd length and positive alternating sum. 452 453 It turns out, the condition is actually sufficient. 454 455 **Proof** 456 457 To prove sufficiency, we show that if an odd-length array has no valid moves, its alternating sum cannot be positive. Let the array be $c_1, c_2, \dots, c_{2k+1}$. 458 459 Now suppose no move is possible. Then for every middle even position $2j$, 460 461 $c_{2j−1} + c_{2j+1} \le c_{2j}$ 462 463 Since $-c_{2j}$ appears in the alternating sum, we can upper-bound it by 464 465 $-c_{2j} \le -(c_{2j - 1} + c_{2j + 1})$ 466 467 Writing out the alternating sum for length $2k+1$: 468 469 $S(c) = c_1 - c_2 + c_3 - c_4 + \dots - c_{2k} + c_{2k+1}$ 470 471 Substituting the inequalities $-c_{2j} \le -(c_{2j-1} + c_{2j+1})$: 472 473 $\begin{aligned} S(c) &\le c_1 - (c_1 + c_3) + c_3 - (c_3 + c_5) + \dots - (c_{2k-1} + c_{2k+1}) + c_{2k+1} \\ &= -c_3 - c_5 - \dots - c_{2k-1} \le 0 \end{aligned}$ 474 475 Thus, if $S(c) \gt 0$, at least one move must exist. 476 477 Now the problem is reduced to counting subarrays with odd-length and positive alternating sum. Let: 478 479 $\texttt{pref}[0] = 0, \quad \texttt{pref}[i] = a_1 - a_2 + a_3 - \dots + (-1)^{i-1}a_i$ 480 481 For a subarray $[l, r]$, if $r − l + 1$ is odd, then $l$ and $r$ have the same parity, and the subarray is good exactly when the corresponding prefix values satisfy: 482 483 * If $l$ is odd, the subarray sum is $\texttt{pref}[r] - \texttt{pref}[l-1]$. We need $\texttt{pref}[r] \gt \texttt{pref}[l-1]$. 484 * If $l$ is even, the subarray sum is $\texttt{pref}[l-1] - \texttt{pref}[r]$. We need $\texttt{pref}[r] \lt \texttt{pref}[l-1]$. 485 486 So while scanning $r$ from left to right, we only need to count previous prefix indices of the opposite type with a smaller or larger prefix value. This is a standard task, which can be done using Fenwick Tree and coordinate compression, or using an ordered set with order statistics. 487 488 **Code (C++, using ordered set)** 489 490 ``` 491 // written by omsincoconut 492 493 #include <bits/stdc++.h> 494 495 using namespace std; 496 typedef long long ll; 497 498 #include <ext/pb_ds/assoc_container.hpp> 499 #include <ext/pb_ds/tree_policy.hpp> 500 using namespace __gnu_pbds; 501 502 #define ordered_set tree<pair<ll, int>, null_type,less<pair<ll, int>>, rb_tree_tag,tree_order_statistics_node_update> 503 504 const bool HAVE_CASE = true; 505 506 void test_case_run() { 507 ll n; 508 cin >> n; 509 510 ll a[n+1]; 511 for (int i = 1; i <= n; i++) cin >> a[i]; 512 513 ll qc[n+1]; 514 qc[0] = 0; 515 ordered_set oset[2]; 516 oset[0].insert({0LL, 0}); 517 518 ll ans = 0; 519 for (int i = 1; i <= n; i++) { 520 qc[i] = a[i] - qc[i-1]; 521 522 ans += oset[(i+1)%2].order_of_key({qc[i], -1}); 523 oset[i%2].insert({-qc[i], i}); 524 } 525 526 cout << ans << "\n"; 527 } 528 529 int main() { 530 ios_base::sync_with_stdio(false); 531 cin.tie(NULL); 532 533 int t = 1; 534 if (HAVE_CASE) cin >> t; 535 while (t--) test_case_run(); 536 537 return 0; 538 } 539 ``` 540 541 **Code (C++, using Fenwick Tree and coordinate compression)** 542 543 ``` 544 #include <bits/stdc++.h> 545 using namespace std; 546 #define int long long 547 548 struct FenwickTree { 549 int n; 550 vector<int> bit; 551 FenwickTree(int n) : n(n + 1), bit(n + 1) {} 552 int query(int r) { 553 int ret = 0; 554 while(r > 0) { 555 ret += bit[r]; 556 r -= (r & -r); 557 } 558 559 return ret; 560 } 561 562 int query(int l, int r) { 563 return query(r) - query(l - 1); 564 } 565 566 void update(int idx, int delta) { 567 while(idx < n) { 568 bit[idx] += delta; 569 idx += (idx & -idx); 570 } 571 } 572 }; 573 574 signed main() { 575 int t; 576 cin >> t; 577 while(t--) { 578 int n; 579 cin >> n; 580 vector<int> v(n); 581 for(auto &it : v) cin >> it; 582 583 vector<int> pre(n + 1); 584 for(int i = 1; i <= n; i++) { 585 if(i & 1) pre[i] = pre[i - 1] + v[i - 1]; 586 else pre[i] = pre[i - 1] - v[i - 1]; 587 } 588 589 vector<int> h = pre; 590 sort(h.begin(), h.end()); 591 h.erase(unique(h.begin(), h.end()), h.end()); 592 auto get = [&](int x) { return lower_bound(h.begin(), h.end(), x) - h.begin() + 1; }; 593 594 FenwickTree fen_ev(h.size()), fen_od(h.size()); 595 int ans = 0; 596 597 fen_ev.update(get(0), 1); 598 599 for(int i = 1; i <= n; i++) { 600 int x = get(pre[i]); 601 if(i & 1) { 602 ans += fen_ev.query(x - 1); 603 fen_od.update(x, 1); 604 } 605 else { 606 ans += fen_od.query(x + 1, h.size()); 607 fen_ev.update(x, 1); 608 } 609 } 610 611 cout << ans << endl; 612 } 613 } 614 ``` 615 616 **Rate the problem!** 617 618 * Excellent problem 619 * Good problem 620 * Average problem 621 * Bad problem 622 * Horrible problem 623 624 #### [H — Fallen Leaves](https://codeforces.com/contest/2227/problem/H) 625 626 **Hint 1** 627 628 For a fixed edge, when does it contribute $1$ to the answer? 629 630 **Hint 2** 631 632 Root the tree anywhere. Let $\texttt{cnt}[u]$ be the number of leaves in the subtree of $u$, and $u \neq \texttt{root}$. The edge $\texttt{parent}_u \to u$ is used if $\texttt{cnt}[u]$ is odd. 633 634 **Hint 3** 635 636 There can be an unchosen leaf. How to choose which leaf to ignore? 637 638 **Solution** 639 640 Let's pick any vertex as the root. For every edge connecting a parent to a child $u$, let $\texttt{cnt}[u]$ be the total number of leaves in the subtree rooted at $u$. 641 642 Consider this edge alone: 643 644 * If $\texttt{cnt}[u]$ is even, all leaves inside this subtree can be paired with each other internally. This edge does not need to be crossed by any path. 645 * If $\texttt{cnt}[u]$ is odd, after pairing as many leaves as possible within the subtree, exactly one leaf will be left over. This leaf must cross the edge to find a pair outside the subtree. Therefore, this edge must be used exactly once. 646 647 If the total leaf count is even, every leaf must be paired. An edge is used if and only if its child's subtree contains an odd number of leaves. Hence: 648 649 $\texttt{Answer} = \#\{u \neq \texttt{root} \mid \texttt{cnt}[u] \equiv 1 \pmod 2\}$ 650 651 But what if the total leaf count was odd? Exactly one leaf will remain unchosen. Leaving a leaf $x$ unchosen allows us to save or lose the cost of some edges. Specifically, for every edge on the path from the root to $x$, the parity of the number of leaves in the corresponding child subtree changes: 652 653 * If the subtree had an odd number of leaves, it becomes even, so that edge is no longer needed; 654 * If the subtree had an even number of leaves, it becomes odd, so that edge becomes needed. 655 656 Therefore, if the total number of leaves is odd, we want to choose a leaf $x$ such that the value 657 658 $\sum\limits_{\text{edges on path root} \ \to \ x} \begin{cases} +1, & \text{if } \texttt{cnt}[\text{child}] \text{ is odd} \\ -1, & \text{if } \texttt{cnt}[\text{child}] \text{ is even} \end{cases}$ 659 660 is maximized. 661 662 Let's define $\texttt{mx}[u]$ as: 663 664 $\texttt{mx}[u] = \max\limits_{x \ \text{is a leaf in subtree of} \ u}(\#\text{odd edges on path} \ u \to x - \#\text{even edges on path} \ u \to x)$ 665 666 Thus, the answer for the odd leaves case is: 667 668 $\texttt{Answer} = \#\{u \neq \texttt{root} \mid \texttt{cnt}[u] \equiv 1 \pmod 2\} - \texttt{mx}[\texttt{root}]$ 669 670 We can compute $\texttt{cnt}[u]$ for every vertex using a DFS. Then, in the same DFS or in a separate one, we compute $\texttt{mx}[u]$. The transition is: 671 672 $\texttt{mx}[u] = \max\limits_{v \ \in \ \text{children}(u)}(\texttt{mx}[v] + (\texttt{cnt}[v] \text{ is odd ?} \ 1 : -1))$ 673 674 and for a leaf, $\texttt{mx}[u] = 0$. 675 676 Therefore, 677 678 * If $\texttt{cnt}[\texttt{root}]$ is even, the answer is just the number of edges whose child subtree has odd $\texttt{cnt}[u]$; 679 * If $\texttt{cnt}[\texttt{root}]$ is odd, subtract $\texttt{mx}[\texttt{root}]$ from that answer. 680 681 **Code (C++)** 682 683 ``` 684 #include <bits/stdc++.h> 685 using namespace std; 686 #define int long long 687 688 const int N = 2e5 + 10; 689 690 int n; 691 vector<int> adj[N]; 692 int mx[N], cnt[N]; 693 694 void dfs(int u, int par) { 695 cnt[u] = (adj[u].size() == 1); 696 697 for(int v : adj[u]) { 698 if(v == par) continue; 699 dfs(v, u); 700 cnt[u] += cnt[v]; 701 } 702 703 int cur = 0; 704 for(int v : adj[u]) { 705 if(v == par) continue; 706 int w = (cnt[v] & 1) ? 1 : -1; 707 cur = max(cur, mx[v] + w); 708 } 709 710 mx[u] = cur; 711 } 712 713 signed main() { 714 ios_base::sync_with_stdio(false); 715 cin.tie(nullptr); 716 717 int t; 718 cin >> t; 719 while(t--) { 720 cin >> n; 721 for(int i = 1; i <= n; i++) adj[i].clear(); 722 723 for(int i = 0; i < n - 1; ++i) { 724 int u, v; 725 cin >> u >> v; 726 adj[u].push_back(v); 727 adj[v].push_back(u); 728 } 729 730 dfs(1, 0); 731 732 int ans = 0; 733 for(int u = 2; u <= n; u++) { 734 if(cnt[u] & 1) ans++; 735 } 736 737 if(!(cnt[1] & 1)) cout << ans << endl; 738 else cout << ans - mx[1] << endl; 739 } 740 741 return 0; 742 } 743 ``` 744 745 **Rate the problem!** 746 747 * Excellent problem 748 * Good problem 749 * Average problem 750 * Bad problem 751 * Horrible problem