codeforces-scrape

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

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