codeforces-scrape

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

2254.md (24131B)


      1 Source: https://codeforces.com/blog/entry/155666
      2 
      3 Thank you for participating in the contest! I hope you enjoyed all problems :) Also, thanks to [reirugan](/profile/reirugan "Candidate Master reirugan") for proofreading the editorial.
      4 
      5 **Rating Predictions**
      6 
      7 | Predictor | A | B | C1 C2 | D | E | F | G |
      8 | --- | --- | --- | --- | --- | --- | --- | --- |
      9 | [yse](/profile/yse "Candidate Master yse") | 800 | 800 | (900 — 1000) | 1200 | 1400 | 1700 | 2000 |
     10 | [Wageeh](/profile/Wageeh "Expert Wageeh") | — | 1000 | (1300 — 1300) | 1500 | — | — | 1900 |
     11 | [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") | 800 | 800 | (1000 — 1100) | 1300 | 1300 | 1900 | 2100 |
     12 | [detective...dots](/profile/detective...dots "Expert detective...dots") | 800 | 900 | (1100 — 1100) | 1300 | 1400 | 1800 | 2100 |
     13 | [Mr_Bald](/profile/Mr_Bald "Specialist Mr_Bald") | 800 | 900 | (1100 — 1200) | 1400 | 1500 | 1800 | — |
     14 | [Argentum47](/profile/Argentum47 "Candidate Master Argentum47") | 800 | 900 | (1000 — 1200) | 1300 | 1400 | 1800 | 2000 |
     15 
     16 **Rate the contest!**
     17 
     18 * Excellent contest
     19 * Good contest
     20 * Average contest
     21 * Bad contest
     22 * Horrible contest
     23 
     24 **Rate the difficulty!**
     25 
     26 * Easy contest
     27 * Normal contest
     28 * Hard contest
     29 
     30 #### [A — Riptide](https://codeforces.com/contest/2254/problem/A)
     31 
     32 **Hint**
     33 
     34 Assume $a \le b \le c$, does $b$ ever change?
     35 
     36 **Solution**
     37 
     38 For simplicity, let's assume $a \le b \le c$ (we can sort the input to achieve this). The operation decreases $c$ by $1$ and increases $a$ by $1$. Therefore, $a$ is getting closer to $b$ and $c$ is also getting closer to $b$. The round ends when $2$ players have the same value, so the answer is $\min(b - a, c - b)$ since if either $a$ or $c$ become equal to $b$, the game will end.
     39 
     40 **Code (C++)**
     41 
     42 ```
     43 #include <bits/stdc++.h>
     44 using namespace std;
     45 
     46 int main() {
     47     int t;
     48     cin >> t;
     49     while(t--) {
     50         vector<int> v(3);
     51         for(int &x : v) cin >> x;
     52         sort(v.begin(), v.end());
     53         cout << min(v[2] - v[1], v[1] - v[0]) << endl;
     54     }
     55 }
     56 ```
     57 
     58 **Rate the problem!**
     59 
     60 * Excellent problem
     61 * Good problem
     62 * Average problem
     63 * Bad problem
     64 * Horrible problem
     65 
     66 #### [B — Evanescent](https://codeforces.com/contest/2254/problem/B)
     67 
     68 **Hint**
     69 
     70 If we perform the operation on any character in a maximal contiguous block of length $ \gt 1$, then $f(s') = f(s)$.
     71 
     72 **Solution**
     73 
     74 The function $f(s)$ converts every maximal contiguous block into a block of size $1$. Therefore, removing a character from a block does not change anything if the block will still exist. The only way we can delete the whole block is if it had a size of $1$. This allows to delete the sole character that exists in the block, additionally achieving $f(s') \lt f(s)$.
     75 
     76 When deleting a block of size $1$, we should consider what happens when the left block touches the right block. If they both contain the same character, then they would merge into one block. Therefore, the answer would decrease by $2$ (our $1$-sized block got removed, and $2$ separate blocks got merged into one).
     77 
     78 Otherwise, if the blocks do not contain the same character, then the answer would decrease by $1$ since nothing will happen other than removing the $1$-sized block.
     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 ans = 1, x = 0;
     96         for(int i = 1; i < n; i++) {
     97             if(s[i] != s[i - 1]) ans++;
     98             if(i == n - 1) break;
     99             
    100             if(s[i] != s[i - 1] && s[i] != s[i + 1]) {
    101                 if(s[i + 1] == s[i - 1]) x = 2;
    102                 else x = max(x, 1);
    103             }
    104         }
    105         
    106         cout << ans - x << endl;
    107     }
    108 }
    109 ```
    110 
    111 **Rate the problem!**
    112 
    113 * Excellent problem
    114 * Good problem
    115 * Average problem
    116 * Bad problem
    117 * Horrible problem
    118 
    119 #### [C1 — Marenol (easy version)](https://codeforces.com/contest/2254/problem/C1)
    120 
    121 **Hint 1**
    122 
    123 The operation is equivalent to freely swapping $a_i$ with $a_{i+2}$ for any valid index $i$.
    124 
    125 **Hint 2**
    126 
    127 After the reduction from Hint 1, we can treat $a$ as two separate strings.
    128 
    129 **Solution**
    130 
    131 Notice that the operation can be treated as swapping $a_i$ with $a_{i+2}$, this works since the operation does not change the middle element, and only changes the first one and the third one.
    132 
    133 Because an element can only move in steps of two, it can never change the parity of its index. Any character at an odd position will always remain at an odd position, and the same applies for even indices.
    134 
    135 Since we have the power to swap the characters at odd indices endlessly (as many times as we want), we can rearrange them into any arrangement we want, independently of the characters at even indices. Therefore, the elements at odd positions in $a$ can match the elements at odd positions in $b$ if they have the same number of ones (or zeros). The same can be applied for even positions.
    136 
    137 **Code (C++)**
    138 
    139 ```
    140 #include <bits/stdc++.h>
    141 using namespace std;
    142  
    143 int main() {
    144     int t;
    145     cin >> t;
    146     while(t--) {
    147         int n;
    148         cin >> n;
    149         string a, b;
    150         cin >> a >> b;
    151         
    152         int cnta[2] = {}, cntb[2] = {};
    153         for(int i = 0; i < n; i++) {
    154             cnta[i % 2] += a[i] == '1';
    155             cntb[i % 2] += b[i] == '1';
    156         }
    157         
    158         cout << (cnta[0] == cntb[0] && cnta[1] == cntb[1] ? "YES" : "NO") << endl;
    159     }
    160 }
    161 ```
    162 
    163 **Rate the problem!**
    164 
    165 * Excellent problem
    166 * Good problem
    167 * Average problem
    168 * Bad problem
    169 * Horrible problem
    170 
    171 #### [C2 — Marenol (hard version)](https://codeforces.com/contest/2254/problem/C2)
    172 
    173 **Solution**
    174 
    175 Building off the core observation from the easy version, we know that elements are strictly trapped in their own parity. Odd-indexed characters only interact with odd-indexed characters, and even with even.
    176 
    177 The problem then boils down to a classic task: what is the minimum number of adjacent swaps needed to transform a binary array into another?
    178 
    179 Since all '$\texttt{1}$'s are identical, they never need to leapfrog over each other. The optimal path is always for the $k$-th '$\texttt{1}$' in your starting array to walk directly to the position of the $k$-th '$\texttt{1}$' in your target array.
    180 
    181 To implement this, just iterate through both strings and collect the positions of the '$\texttt{1}$'s in the odd indices into one list, and the positions of the '$\texttt{1}$'s in the even indices into another. If the lengths of the corresponding lists for $a$ and $b$ don't match, it's impossible to transform, so output $-1$. Otherwise, just sum up the absolute differences between the $k$-th elements of the starting and target lists for both the odd and even arrays. That sum, divided by $2$, is your exact minimum number of operations. We divide by $2$ because one operation moves characters by $2$ steps.
    182 
    183 **Code (C++)**
    184 
    185 ```
    186 #include <bits/stdc++.h>
    187 using namespace std;
    188 #define ll long long
    189  
    190 int main() {
    191     int t;
    192     cin >> t;
    193     while(t--) {
    194         int n;
    195         cin >> n;
    196         string a, b;
    197         cin >> a >> b;
    198         
    199         ll ans = 0;
    200         bool ok = true;
    201         
    202         for(int k = 0; k < 2; k++) {
    203             vector<int> p1, p2;
    204             for(int i = k; i < n; i += 2) {
    205                 if(a[i] == '1') p1.push_back(i);
    206                 if(b[i] == '1') p2.push_back(i);
    207             }
    208             
    209             if(p1.size() != p2.size()) {
    210                 ok = false;
    211                 break;
    212             }
    213             
    214             for(int i = 0; i < p1.size(); i++) ans += abs(p1[i] - p2[i]);
    215         }
    216         
    217         if(!ok) cout << -1 << endl;
    218         else cout << ans / 2 << endl;
    219     }
    220 }
    221 ```
    222 
    223 **Rate the problem!**
    224 
    225 * Excellent problem
    226 * Good problem
    227 * Average problem
    228 * Bad problem
    229 * Horrible problem
    230 
    231 #### [D — Silhouette](https://codeforces.com/contest/2254/problem/D)
    232 
    233 **Hint 1**
    234 
    235 Equal values in $a$ will always have the exact same shadow, and larger elements always have strictly larger shadows. So if you sort the distinct values of $b$, they correspond in order to the distinct values of $a$: the group with the $i$-th smallest value has shadow equal to the $i$-th smallest distinct value in $b$.
    236 
    237 **Hint 2**
    238 
    239 Let $s_1 \lt s_2 \lt \dots \lt s_m$ be the distinct sorted values of $b$, and let group $i$ be all elements sharing the value corresponding to $s_i$. Then $s_i$ is the sum of all groups smaller than group $i$, and $s_{i+1}$ is that same sum plus group $i$ itself. So $s_{i+1} - s_i = c_i \cdot v_i$, where $c_i$ is the count of elements in group $i$ and $v_i$ is their value.
    240 
    241 **Hint 3**
    242 
    243 What must $s_1$ be? And once every $v_i$ is pinned down by the equation above, is there a group left with no equation constraining its value? What's the smallest legal choice for it?
    244 
    245 **Solution**
    246 
    247 It's easy to see that equal values in $a$ produce equal shadows. The converse also holds: distinct values in $a$ always produce distinct shadows, and moreover a larger value always produces a larger shadow. So if we sort the distinct values of $a$ as $v_1 \lt v_2 \lt \dots \lt v_k$ with frequencies $c_1, \dots, c_k$, then the shadow of group $i$ is simply the sum of all smaller groups, $S_{i-1} = \sum_{j \lt i} c_j v_j$, and these prefix sums satisfy $S_0 = 0 \lt S_1 \lt \dots \lt S_{k-1}$. In other words, the distinct values of $b$, sorted, correspond exactly and in order to these prefix sums.
    248 
    249 This gives a direct reconstruction. Sort the distinct values of $b$ as $s_1 \lt s_2 \lt \dots \lt s_m$; since $S_0$ must be $0$, we need $s_1 = 0$, otherwise the answer is $-1$. The count of $s_i$ in $b$ gives $c_i$, the size of group $i$, and since $s_{i+1} - s_i = c_i \cdot v_i$, we can recover $v_i = \frac{(s_{i+1} - s_i)}{c_i}$. If this division isn't exact, or if the resulting $v_i$ doesn't exceed $v_{i-1}$, no valid array exists. The very last group has no such equation to pin it down, so to keep $a$ lexicographically smallest we assign it the smallest legal value, one more than the previous group's value.
    250 
    251 Once every group's value is known, replace each $b_i$ by its group's value to get $a$.
    252 
    253 **Code (C++)**
    254 
    255 ```
    256 #include <bits/stdc++.h>
    257 using namespace std;
    258 #define ll long long
    259  
    260 int main() {
    261     int t;
    262     cin >> t;
    263     while(t--) {
    264         int n;
    265         cin >> n;
    266         vector<ll> b(n);
    267         map<ll, ll> freq;
    268         
    269         for(int i = 0; i < n; i++) {
    270             cin >> b[i];
    271             freq[b[i]]++;
    272         }
    273     
    274         if (!freq.count(0)) {
    275             cout << -1 << endl;
    276             continue;
    277         }
    278     
    279         map<ll, ll> ans;
    280         ll prv_shadow = 0, prv_cnt = 0, lst = 0;
    281         bool ok = true;
    282     
    283         for(auto [cur_shadow, cur_cnt] : freq) {
    284             if(cur_shadow != 0) {
    285                 ll diff = cur_shadow - prv_shadow;
    286                 
    287                 if(diff % prv_cnt != 0) {
    288                     ok = false;
    289                     break;
    290                 }
    291                 
    292                 ll u = diff / prv_cnt;
    293                 if(u <= lst) {
    294                     ok = false;
    295                     break;
    296                 }
    297                 
    298                 ans[prv_shadow] = u;
    299                 lst = u;
    300             }
    301             
    302             prv_shadow = cur_shadow;
    303             prv_cnt = cur_cnt;
    304         }
    305         
    306         if(!ok) {
    307             cout << -1 << endl;
    308             continue;
    309         }
    310         
    311         ans[prv_shadow] = lst + 1;
    312         for(int i = 0; i < n; ++i) cout << ans[b[i]] << " \n"[i == n - 1];
    313     }
    314 }
    315 ```
    316 
    317 **Rate the problem!**
    318 
    319 * Excellent problem
    320 * Good problem
    321 * Average problem
    322 * Bad problem
    323 * Horrible problem
    324 
    325 #### [E — Chronostasis](https://codeforces.com/contest/2254/problem/E)
    326 
    327 **Hint 1**
    328 
    329 The problem states that $b_i = a_i - a_{i-1}$. This directly implies that $a_i = a_{i-1} + b_i$. If you assume $a_0 = 0$, you can view $a$ simply as the prefix sums of some permutation of $b$.
    330 
    331 **Hint 2**
    332 
    333 The standard way to achieve a lexicographically smallest sequence is to build it greedily from left to right, making $a_1$ as small as possible, then $a_2$ as small as possible, and so forth.
    334 
    335 **Hint 3**
    336 
    337 Since $a_{i-1}$ is fixed from the previous steps, minimizing $a_i$ means you must pick the smallest available $b_i$. However, the problem imposes a strict rule: every element in $a$ must be strictly positive ($a_i \ge 1$). How does this restrict your choice of $b_i$?
    338 
    339 **Solution**
    340 
    341 Let's rewrite the given operation backwards. We are told that $b_i = a_i - a_{i-1}$. By rearranging this, we get $a_i = a_{i-1} + b_i$. If we define $a_0 = 0$, the array $a$ is essentially just the prefix sums of some permutation of the array $b$.
    342 
    343 We are asked to find a permutation of $b$ that produces an array $a$ satisfying two conditions: every $a_i$ must be strictly positive, and $a$ must be lexicographically smallest.
    344 
    345 To construct the lexicographically smallest array $a$, we should build it greedily from left to right. Suppose we have already successfully constructed the prefix of $a$ up to $a_{i-1}$. To determine $a_i$, we need to choose an unused element from $b$ to act as $b_i$. Since $a_{i-1}$ is already fixed, minimizing $a_i$ is exactly the same as picking the smallest possible $b_i$.
    346 
    347 However, we can't just pick the absolute minimum available element because we must guarantee that $a_i \ge 1$. Substituting our earlier equation, this means $a_{i-1} + b_i \ge 1$, which simplifies to $b_i \ge 1 - a_{i-1}$.
    348 
    349 This gives us a clear greedy strategy. At each step $i$, we must select the smallest available element in $b$ that is greater than or equal to $1 - a_{i-1}$. To implement this efficiently, we can insert all elements of the given array $b$ into a multiset. We maintain a running sum variable to represent $a_{i-1}$ (initially $0$). At each step, we query the multiset for the `lower_bound` of $1 - a_{i-1}$. If the iterator returns the end of the multiset, it means no available element is large enough to keep the current value strictly positive. In this case, a valid array cannot be formed, and we immediately output $-1$. If a valid element is found, we add it to our running sum to compute $a_i$, store it in our answer array, and erase that element from the multiset. We repeat this process $n$ times.
    350 
    351 **Code (C++)**
    352 
    353 ```
    354 #include <bits/stdc++.h>
    355 #define int long long
    356 using namespace std;
    357 
    358 void solve() {
    359     int n, cur = 0;
    360     cin >> n;
    361     multiset<int> b;
    362     for(int i = 0; i < n; i++) {
    363         int x;
    364         cin >> x;
    365         b.insert(x);
    366     }
    367     
    368     vector<int> ans(n);
    369     for(int i = 0; i < n; i++){
    370         auto it = b.lower_bound(1 - cur);
    371         if(it == b.end()) return void(cout << -1 << '\n');
    372         cur += *it;
    373         b.erase(it);
    374         ans[i] = cur;
    375     }
    376     
    377     for(int i = 0; i < n; i++) cout << ans[i] << " \n"[i == n - 1];
    378 }
    379 
    380 signed main() {
    381     ios::sync_with_stdio(false);
    382     cin.tie(NULL);
    383     int t;
    384     cin >> t;
    385     while(t--) solve();
    386 }
    387 ```
    388 
    389 **Rate the problem!**
    390 
    391 * Excellent problem
    392 * Good problem
    393 * Average problem
    394 * Bad problem
    395 * Horrible problem
    396 
    397 #### [F — Whiplash](https://codeforces.com/contest/2254/problem/F)
    398 
    399 **Hint 1**
    400 
    401 Try tracing the array elements after performing two consecutive operations, say on index $i$ and then on index $j$. If you look at the set of resulting values and ignore their order, how does it compare to the set of values you would get if you only performed a single operation on index $j$?
    402 
    403 **Hint 2**
    404 
    405 Any sequence of operations results in an array that is just a permutation of either the original array $a$, or the array $a$ after exactly one operation.
    406 
    407 **Solution**
    408 
    409 Let's analyze how a single operation affects the overall XOR sum of the array. Let $S_a$ be the XOR sum of all elements in $a$. When we choose an index $i$, we XOR $n-1$ elements with $a_i$. Since $n$ is even, $n-1$ is odd. The new XOR sum of the array will be $S_a \oplus (a_i \text{ XORed } n-1 \text{ times})$, which simplifies perfectly to $S_a \oplus a_i$.
    410 
    411 Now, let's observe what happens if we perform multiple operations. Suppose we perform an operation on index $i$, followed by an operation on index $j$. After the first operation, the element at index $j$ becomes $a_j \oplus a_i$, and the element at index $i$ remains $a_i$. All other elements $a_k$ become $a_k \oplus a_i$.
    412 
    413 During the second operation, we XOR everything (except index $j$) with the current value at index $j$, which is $a_j \oplus a_i$.
    414 
    415 Let's look at the resulting values:
    416 
    417 * For any other index $k$, the value becomes $(a_k \oplus a_i) \oplus (a_j \oplus a_i) = a_k \oplus a_j$.
    418 * For index $i$, the value becomes $a_i \oplus (a_j \oplus a_i) = a_j$.
    419 * For index $j$, the value remains $a_j \oplus a_i$.
    420 
    421 If we look at this final set of values, it is exactly the same as if we had skipped the first operation and only performed a single operation on index $j$ from the very beginning. The order of the elements is different, but the set of values is identical.
    422 
    423 This reveals the core property of the problem: no matter how many operations you perform, the resulting array (ignoring the order of elements) will either be identical to the original array $a$, or identical to the array $a$ after exactly one operation.
    424 
    425 This gives us a straightforward solution. First, sort both arrays. If $a$ and $b$ are already identical, we output "YES" (0 operations needed). If they are not identical, we need to simulate exactly one operation. Which element $a_i$ should we use? We know from our first observation that the target XOR sum $S_b$ must equal $S_a \oplus a_i$. By rearranging this, the required element must be $a_i = S_a \oplus S_b$. We compute this target value $x = S_a \oplus S_b$. If $x$ does not exist in our initial array $a$, we can immediately output "NO". If it does exist, we find its index, apply the operation to array $a$, sort the modified array, and check if it now matches $b$.
    426 
    427 **Code (C++)**
    428 
    429 ```
    430 #include <bits/stdc++.h>
    431 using namespace std;
    432  
    433 signed main() {
    434     int t;
    435     cin >> t;
    436     while(t--) {
    437         int n;
    438         cin >> n;
    439         vector<int> a(n), b(n);
    440         for(auto &it : a) cin >> it;
    441         for(auto &it : b) cin >> it;
    442  
    443         sort(a.begin(), a.end());
    444         sort(b.begin(), b.end());
    445 
    446         if(a == b) {
    447             cout << "YES" << endl;
    448             continue;
    449         }
    450  
    451         int x = 0;
    452         for(auto it : a) x ^= it;
    453         for(auto it : b) x ^= it;
    454 		
    455         int idx = -1;
    456         for(int i = 0; i < n; i++) {
    457             if(a[i] == x) {
    458                 idx = i;
    459                 break;
    460             }
    461         }
    462 
    463         if(idx == -1) {
    464             cout << "NO" << endl;
    465             continue;
    466         }
    467  
    468         for(int i = 0; i < n; i++) {
    469             if(i == idx) continue;
    470             a[i] ^= x;
    471         }
    472  
    473         sort(a.begin(), a.end());
    474         cout << (a == b ? "YES" : "NO") << endl;
    475     }
    476 }
    477 ```
    478 
    479 **Rate the problem!**
    480 
    481 * Excellent problem
    482 * Good problem
    483 * Average problem
    484 * Bad problem
    485 * Horrible problem
    486 
    487 #### [G — Nightcrawler](https://codeforces.com/contest/2254/problem/G)
    488 
    489 **Hint 1**
    490 
    491 Because no subset can contain branching paths, two distinct leaves can never belong to the same subset. If the tree has $\ell$ leaves, you need at least $\ell$ subsets. Any $k \lt \ell$ is impossible. For $k \ge \ell$, the condition is always satisfiable since you can always break paths into smaller singletons.
    492 
    493 **Hint 2**
    494 
    495 Try to build the solution bottom-up. Each leaf starts a path. When these paths meet at a parent node, the parent can only join one of them. To maximize the total score, which path's maximum should the parent node interact with?
    496 
    497 **Hint 3**
    498 
    499 It is always optimal for the parent to join the path that currently has the smallest maximum. If the parent's value is larger, it successfully increases that path's maximum, leaving the old maximum behind as a spare value. If the parent is smaller, the path is unaffected, and the parent itself becomes the spare value that we can use if we are allowed extra subsets.
    500 
    501 **Solution**
    502 
    503 The core restriction is that every subset must form a straight vertical chain (an ancestor-descendant path). This immediately tells us that two distinct leaves can never be placed in the same subset. Consequently, the minimum number of subsets $k$ we can ever form is exactly the number of leaves in the tree, which we will call $\ell$. For any $k \lt \ell$, a valid partition is impossible, and we output $-1$. For $k \ge \ell$, it is always possible because we can just break valid chains into individual singleton nodes.
    504 
    505 Let's build the optimal chains from the bottom up. Every leaf initially forms its own chain where the maximum value is just the leaf's value. As we move up the tree, paths merge at a parent node $u$. The node $u$ must join exactly one of the chains coming from its descendants.
    506 
    507 To maximize the overall sum of chain maximums, $u$ should greedily join the chain with the lowest current maximum. Let's say the smallest maximum among all incoming chains is $x$. If $a_u$ is greater than $x$, placing $u$ in this chain upgrades its maximum from $x$ to $a_u$. The old maximum $x$ doesn't disappear; it gets detached and becomes an extra node that we can use to form a new chain if we are allowed to use more than $\ell$ subsets. Conversely, if $a_u \le x$, placing $u$ in the chain doesn't improve the maximum at all, so $a_u$ itself becomes the detached spare node.
    508 
    509 This process translates elegantly into a data structure approach. For each subtree, we can maintain the maximums of its active chains using a min-heap (a priority queue). When we process a node $u$, we merge all the heaps of its children. To do this efficiently, we always merge smaller heaps into larger heaps, a technique known as small-to-large merging. Once the children's paths are merged, we extract the absolute minimum element from $u$'s heap, compare it with $a_u$, push the larger of the two back into the active heap, and append the smaller one to a global list of extra available values.
    510 
    511 By the time we finish processing the root, the root's heap will contain exactly $\ell$ elements, representing the maximums of the $\ell$ essential chains. The sum of these elements gives our optimal answer for exactly $\ell$ subsets. To find the answer for larger values of $k$, we simply sort our global list of extra values in descending order and greedily add the largest available extra to our running total for each additional subset allowed.
    512 
    513 Because of the small-to-large merging, each element is moved between heaps at most $\mathcal{O}(\log n)$ times. Each heap operation takes logarithmic time, resulting in an overall time complexity of $\mathcal{O}(n \log^2 n)$, which comfortably passes the time limits.
    514 
    515 **Code (C++)**
    516 
    517 ```
    518 #include <bits/stdc++.h>
    519  
    520 using namespace std;
    521 #define ll long long
    522  
    523 void solve() {
    524     int n;
    525     cin >> n;
    526  
    527     vector<ll> a(n + 1);
    528     for(int i = 1; i <= n; i++) cin >> a[i];
    529  
    530     vector<int> p(n + 1);
    531     for(int i = 2; i <= n; i++) cin >> p[i];
    532  
    533     vector<priority_queue<ll, vector<ll>, greater<ll>>> pq(n + 1);
    534     vector<ll> av;
    535  
    536     for(int i = n; i >= 1; i--) {
    537         if(pq[i].empty()) pq[i].push(a[i]);
    538         else {
    539             ll x = pq[i].top();
    540             pq[i].pop();
    541             pq[i].push(max(x, a[i]));
    542             av.push_back(min(x, a[i]));
    543         }
    544  
    545         if(i > 1) {
    546             int par = p[i];
    547             if(pq[par].size() < pq[i].size()) swap(pq[par], pq[i]);
    548  
    549             while(!pq[i].empty()) {
    550                 pq[par].push(pq[i].top());
    551                 pq[i].pop();
    552             }
    553         }
    554     }
    555  
    556     int l = pq[1].size();
    557     ll sum = 0;
    558     
    559     while(!pq[1].empty()) {
    560         sum += pq[1].top();
    561         pq[1].pop();
    562     }
    563  
    564     vector<ll> ans(n + 1, -1);
    565     ans[l] = sum;
    566  
    567     sort(av.rbegin(), av.rend());
    568     for(int i = 0; i < av.size(); i++) {
    569         sum += av[i];
    570         ans[l + i + 1] = sum;
    571     }
    572  
    573     for(int k = 1; k <= n; k++) cout << ans[k] << " \n"[k == n];
    574 }
    575  
    576 int main() {
    577     int t;
    578     cin >> t;
    579     while(t--) solve();
    580 }
    581 ```
    582 
    583 **Rate the problem!**
    584 
    585 * Excellent problem
    586 * Good problem
    587 * Average problem
    588 * Bad problem
    589 * Horrible problem