codeforces-scrape

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

2252.md (21541B)


      1 Source: https://codeforces.com/blog/entry/155741
      2 
      3 Thank you for participating in Codeforces Round 1115 (Div. 2)! We hope you enjoyed the problems.
      4 
      5 The round was prepared by [Bufu](/profile/Bufu "Candidate Master Bufu") and [TomitaMatei](/profile/TomitaMatei "Master TomitaMatei"), and coordinated by [cry](/profile/cry "International Master cry").
      6 
      7 ---
      8 
      9 #### [2252A - Boss Fight](/contest/2252/problem/A "Codeforces Round 1115 (Div. 2)")
     10 
     11 **Solution**
     12 
     13 The boss's shield permanently activates and blocks all subsequent damage only when two cards of the exact same value are played back-to-back. Importantly, the card that actually triggers the shield still deals its normal damage.
     14 
     15 This means we want to play as many cards as possible *before* being forced to place two identical cards adjacent to each other. We should only do this on the very last card we play.
     16 
     17 Let the most frequent card in our hand have a damage value of $X$, and let its frequency be $F$. Let the number of all *other* cards be $O = n - F$.
     18 
     19 To maximize the number of $X$ cards we can play, we must use the $O$ "other" cards as separators. By placing an "other" card between every $X$ card, we can form an alternating sequence like this:
     20 
     21 $X, \text{other}_1, X, \text{other}_2, \ldots, X, \text{other}_O, X$
     22 
     23 This allows us to safely play $O + 1$ copies of $X$ without triggering the shield.
     24 
     25 Finally, to squeeze out the maximum possible damage, we can play exactly one more $X$ card at the very end of this sequence:
     26 
     27 $X, \text{other}_1, X, \text{other}_2, \ldots, X, \text{other}_O, X, \mathbf{X}$
     28 
     29 This final $X$ triggers the shield, but it still deals its normal damage. All remaining cards in our hand will deal $0$, but that doesn't matter because we have already used all of our "other" cards.
     30 
     31 Thus, the maximum number of $X$ cards we can successfully play is $(O + 1) + 1 = O + 2$. Of course, if $F \lt O + 2$, we simply play all $F$ of our $X$ cards without any issues.
     32 
     33 The maximum number of majority cards we can play is $\min(F, O + 2)$. Since we always play every single "other" card, the maximum total damage is:
     34 
     35 $\text{Sum of all "other" cards} + X \cdot \min(F, O + 2)$
     36 
     37 **Time complexity:** $\mathcal{O}(n)$.
     38 
     39 **Code (C++)**
     40 
     41 ```
     42 #include <iostream>
     43 #include <vector>
     44 #include <map>
     45 #include <algorithm>
     46  
     47 using namespace std;
     48  
     49 void solve() {
     50     int n;
     51     cin >> n;
     52     long long total_sum = 0;
     53     map<int, int> freq;
     54     
     55     int max_f = 0;
     56     int maj_val = 0;
     57     
     58     for (int i = 0; i < n; i++) {
     59         int x;
     60         cin >> x;
     61         total_sum += x;
     62         freq[x]++;
     63         if (freq[x] > max_f) {
     64             max_f = freq[x];
     65             maj_val = x;
     66         }
     67     }
     68     
     69     int others = n - max_f;
     70     
     71     int max_majority_played = min(max_f, others + 2);
     72     
     73     long long ans = (total_sum - 1LL * max_f * maj_val) + 1LL * max_majority_played * maj_val;
     74     cout << ans << "\n";
     75 }
     76  
     77 int main() {
     78     ios_base::sync_with_stdio(false);
     79     cin.tie(NULL);
     80     int t; cin >> t;
     81     while(t--) {
     82         solve();
     83     }
     84     return 0;
     85 }
     86 ```
     87 
     88 ---
     89 
     90 #### [2252B - Always Changing](/contest/2252/problem/B "Codeforces Round 1115 (Div. 2)")
     91 
     92 **Solution**
     93 
     94 Let $n_0$ and $n_1$ be the number of `0`s and `1`s in the initial string. Let $k_0$ and $k_1$ be the number of `0`s and `1`s in the final alternating string. Let $c_0$ and $c_1$ be the number of `0`s and `1`s we deleted.
     95 
     96 Because our deletions must strictly alternate, the difference between the number of deleted `0`s and `1`s can be at most $1$. Thus, $|c_0 - c_1| \le 1$. We know that $c_0 = n_0 - k_0$ and $c_1 = n_1 - k_1$.
     97 
     98 Let $\Delta n = n_0 - n_1$ and $\Delta k = k_0 - k_1$. Substituting our equations, the condition $|c_0 - c_1| \le 1$ translates to:
     99 
    100 $|\Delta n - \Delta k| \le 1$
    101 
    102 Since the final string is strictly alternating, $\Delta k$ can only be $-1$, $0$, or $1$. This means that if $|\Delta n| \gt 2$, it is mathematically impossible to satisfy the inequality, and we should output $-1$.
    103 
    104 If it is possible ($|\Delta n| \le 2$), we want to maximize the length of our final string (which minimizes deletions). We can first greedily "compress" the initial string by removing all adjacent duplicate characters (e.g., `00011001` becomes `0101`). Let the length of this compressed alternating string be $L$, and let $\Delta L$ be the difference between the number of `0`s and `1`s in it.
    105 
    106 To ensure our sequence of deletions is valid, we must satisfy the condition $|\Delta n - \Delta k| \le 1$, meaning our final $\Delta k$ must be in the range $[\Delta n - 1, \Delta n + 1]$. We can safely remove any number of characters from the *beginning* or the *end* of our compressed alternating string, and it will remain alternating. Each character we remove shifts $\Delta L$ by exactly $+1$ or $-1$.
    107 
    108 Thus, to fix the parity and enter the valid range, the minimum number of characters we must drop from the ends of our compressed string is exactly the mathematical distance from $\Delta L$ to the range $[\Delta n - 1, \Delta n + 1]$. This distance is exactly $\max(0, |\Delta n - \Delta L| - 1)$.
    109 
    110 The total number of deleted characters is the number of characters removed during compression $(n - L)$, plus the characters removed from the ends to fix the parity. Final answer: $(n - L) + \max(0, |\Delta n - \Delta L| - 1)$.
    111 
    112 **Time complexity:** $\mathcal{O}(n)$.
    113 
    114 **Code (C++)**
    115 
    116 ```
    117 #include <iostream>
    118 #include <string>
    119 #include <cmath>
    120 #include <algorithm>
    121  
    122 using namespace std;
    123  
    124 void solve() {
    125     int n; cin >> n;
    126     string s; cin >> s;
    127  
    128     int n0 = 0, n1 = 0;
    129     for (char c : s) {
    130         if (c == '0') n0++;
    131         else n1++;
    132     }
    133  
    134     int delta_n = n0 - n1;
    135     if (abs(delta_n) > 2) {
    136         cout << -1 << "\n";
    137         return;
    138     }
    139  
    140     int L = 1;
    141     int L0 = (s[0] == '0' ? 1 : 0);
    142     int L1 = (s[0] == '1' ? 1 : 0);
    143  
    144     for (int i = 1; i < n; i++) {
    145         if (s[i] != s[i - 1]) {
    146             L++;
    147             if (s[i] == '0') L0++;
    148             else L1++;
    149         }
    150     }
    151  
    152     int delta_L = L0 - L1;
    153     int ans = (n - L) + max(0, abs(delta_n - delta_L) - 1);
    154     cout << ans << "\n";
    155 }
    156  
    157 int main() {
    158     ios_base::sync_with_stdio(false);
    159     cin.tie(NULL);
    160     
    161     int t; cin >> t;
    162     while(t--) {
    163         solve();
    164     }
    165     
    166     return 0;
    167 }
    168 ```
    169 
    170 ---
    171 
    172 #### [2252C - Risky Tower](/contest/2252/problem/C "Codeforces Round 1115 (Div. 2)")
    173 
    174 **Solution**
    175 
    176 The tower collapses if all $m$ pieces of any single level are removed. This guarantees that the answer is at most $m$.
    177 
    178 Let's write the condition to collapse a specific row $k$ via damage. The sum of destabilization factors of the removed pieces from rows $i \ge k$ must satisfy:
    179 
    180 $\sum a_{i,j} \ge v_k$
    181 
    182 To satisfy this inequality using the minimum number of pieces, we must greedily select pieces with the largest $a_{i,j}$ from rows at and below $k$.
    183 
    184 Since the answer will never exceed $m$, we only need to keep track of at most $m$ pieces at any time. We can process the grid from the bottom row ($n$) to the top row ($1$), maintaining a priority queue or sorted list of the largest $m$ destabilization factors $a_{i,j}$ seen so far.
    185 
    186 At each row $k$, we insert its $m$ pieces into our active pool, discard all but the largest $m$ elements overall, and find the minimum number of largest elements that sum to at least $v_k$. The minimum number of pieces required across all rows $k$, bounded by $m$, is our answer.
    187 
    188 **Time complexity:** $\mathcal{O}(n \cdot m \log m)$
    189 
    190 **Code (C++)**
    191 
    192 ```
    193 #include <iostream>
    194 #include <vector>
    195 #include <algorithm>
    196  
    197 using namespace std;
    198  
    199 void solve() {
    200     int n, m;
    201     cin >> n >> m;
    202     vector<long long> v(n + 1);
    203     for(int i = 1; i <= n; i++) cin >> v[i];
    204     
    205     vector<vector<long long>> a(n + 1, vector<long long>(m));
    206     for(int i = 1; i <= n; i++) {
    207         for(int j = 0; j < m; j++) {
    208             cin >> a[i][j];
    209         }
    210     }
    211     
    212     int min_ans = m; 
    213     vector<long long> best;
    214     
    215     for(int k = n; k >= 1; k--) {
    216         for(int j = 0; j < m; j++) {
    217             best.push_back(a[k][j]);
    218         }
    219         
    220         sort(best.rbegin(), best.rend());
    221         
    222         if ((int)best.size() > m) {
    223             best.resize(m);
    224         }
    225         
    226         long long current_sum = 0;
    227         int pieces = 0;
    228         
    229         for(long long val : best) {
    230             current_sum += val;
    231             pieces++;
    232             if (current_sum >= v[k]) {
    233                 min_ans = min(min_ans, pieces);
    234                 break;
    235             }
    236         }
    237     }
    238     
    239     cout << min_ans << "\n";
    240 }
    241  
    242 int main() {
    243     ios_base::sync_with_stdio(false);
    244     cin.tie(NULL);
    245     int t; cin >> t;
    246     while(t--) {
    247         solve();
    248     }
    249     return 0;
    250 }
    251 ```
    252 
    253 ---
    254 
    255 #### [2252D - Array Replacement](/contest/2252/problem/D "Codeforces Round 1115 (Div. 2)")
    256 
    257 **Solution**
    258 
    259 Let's consider the difference array $d$, where $d_i = a_{i+1} - a_i$ for all $1 \le i \lt n$.
    260 
    261 Consider what happens to the array $a$ when we perform an operation on index $i$. The triplet $(a_{i-1}, a_i, a_{i+1})$ becomes $(a_{i-1}, a_{i-1} - a_i + a_{i+1}, a_{i+1})$. Let's see how this affects our difference array $d$:
    262 
    263 * The new $d_{i-1}$ becomes $(a_{i-1} - a_i + a_{i+1}) - a_{i-1} = a_{i+1} - a_i$, which is exactly the old $d_i$.
    264 * The new $d_i$ becomes $a_{i+1} - (a_{i-1} - a_i + a_{i+1}) = a_i - a_{i-1}$, which is exactly the old $d_{i-1}$.
    265 
    266 Thus, performing the operation on index $i$ is exactly equivalent to **swapping** $d_{i-1}$ and $d_i$!
    267 
    268 However, we can only perform this operation if $a_{i-1}$ and $a_{i+1}$ have the same parity. Notice that $a_{i+1} - a_{i-1} = (a_{i+1} - a_i) + (a_i - a_{i-1}) = d_i + d_{i-1}$. For $a_{i-1}$ and $a_{i+1}$ to have the same parity, their difference $d_i + d_{i-1}$ must be an even number. The sum of two integers is even if and only if they have the **same parity**.
    269 
    270 Therefore, the condition that $a_{i-1}$ and $a_{i+1}$ have the same parity is equivalent to saying $d_{i-1}$ and $d_i$ have the same parity.
    271 
    272 This means we can swap any two adjacent elements in the difference array $d$ as long as they share the same parity. This allows us to independently sort any contiguous subsegment of $d$ that consists entirely of even numbers, or entirely of odd numbers.
    273 
    274 To construct the lexicographically smallest array $a$, we simply group contiguous elements of $d$ that share the same parity, sort each group in non-decreasing order, and then reconstruct the array $a$ starting from $a_1$.
    275 
    276 **Time complexity:** $\mathcal{O}(n \log n)$.
    277 
    278 **Code (C++)**
    279 
    280 ```
    281 #include <iostream>
    282 #include <vector>
    283 #include <algorithm>
    284 #include <cmath>
    285  
    286 using namespace std;
    287  
    288 void solve() {
    289     int n;
    290     cin >> n;
    291     vector<long long> a(n);
    292     for (int i = 0; i < n; i++) {
    293         cin >> a[i];
    294     }
    295     
    296     vector<long long> d(n - 1);
    297     for (int i = 0; i < n - 1; i++) {
    298         d[i] = a[i + 1] - a[i];
    299     }
    300     
    301     for (int i = 0; i < n - 1; ) {
    302         int j = i;
    303         while (j < n - 1 && (d[j] & 1) == (d[i] & 1)) {
    304             j++;
    305         }
    306         sort(d.begin() + i, d.begin() + j);
    307         i = j;
    308     }
    309     
    310     cout << a[0] << " ";
    311     long long cur = a[0];
    312     for (int i = 0; i < n - 1; i++) {
    313         cur += d[i];
    314         cout << cur << " ";
    315     }
    316     cout << "\n";
    317 }
    318  
    319 int main() {
    320     ios_base::sync_with_stdio(false);
    321     cin.tie(NULL);
    322     int t; cin >> t;
    323     while(t--) {
    324         solve();
    325     }
    326     return 0;
    327 }
    328 ```
    329 
    330 ---
    331 
    332 #### [2252E - Generational Triplets](/contest/2252/problem/E "Codeforces Round 1115 (Div. 2)")
    333 
    334 **Solution**
    335 
    336 From the arithmetic progression condition,
    337 
    338 $2b = a + c.$
    339 
    340 From the XOR condition,
    341 
    342 $b = a \oplus c.$
    343 
    344 Substituting the second equation into the first gives
    345 
    346 $2(a \oplus c) = a + c.$
    347 
    348 Let $x$ be the bitwise AND of $a$ and $c$, i.e. `x = a&c`. Recall the standard bitwise addition identity
    349 
    350 $a + c = (a \oplus c) + 2x.$
    351 
    352 Therefore,
    353 
    354 $a \oplus c = 2x.$
    355 
    356 Equivalently, in bitwise notation, `a^c = 2(a&c)`.
    357 
    358 Thus, it is enough to count pairs $(a,c)$ such that $a \lt c \le n$ and `a^c = 2(a&c)`.
    359 
    360 For every such pair, $b$ is uniquely determined as $a \oplus c$. Also, $a \lt b \lt c$ follows from the two original conditions. We only need to enforce $a \lt c$: if $a=c$, then the equation becomes $0=2a$, which is impossible because $a \ge 1$.
    361 
    362 We solve this with digit DP, processing bits from $60$ down to $0$. Let the state be
    363 
    364 $\mathrm{dp}[\mathrm{bit}][\mathrm{cLess}][\mathrm{aLess}][\mathrm{need}].$
    365 
    366 * `bit`: the bit currently being processed.
    367 * `cLess`: whether the already processed prefix of $c$ is strictly smaller than the corresponding prefix of $n$.
    368 * `aLess`: whether the already processed prefix of $a$ is strictly smaller than the corresponding prefix of $c$.
    369 * `need`: the value required for the current bit of `a&c`, determined by the XOR value at the previous, more significant bit.
    370 
    371 At each state, try all four choices for the current bits of $a$ and $c$. A transition is valid when:
    372 
    373 1. The chosen prefix of $c$ does not exceed the prefix of $n$.
    374 2. The chosen prefix of $a$ does not exceed the prefix of $c$.
    375 3. The current bit of `a&c` equals `need`.
    376 
    377 For the next lower bit, the new value of `need` is the XOR of the current bits of $a$ and $c$. This represents the one-bit left shift in `a^c = 2(a&c)`.
    378 
    379 After processing all bits, the state contributes $1$ exactly when `need` is $0$ and `aLess` is true, which guarantees $a \lt c$.
    380 
    381 **Time complexity:** $\mathcal{O}(\log n)$ per test case.
    382 
    383 **Code (C++)**
    384 
    385 ```
    386 #include <iostream>
    387 #include <vector>
    388 #include <cstring>
    389  
    390 using namespace std;
    391  
    392 long long dp[65][2][2][2];
    393 long long n;
    394  
    395 const int MOD = 1000000007;
    396  
    397 long long solve_dp(int bit, int c_less, int a_less, int need) {
    398     if (bit < 0) {
    399         if (need == 0 && a_less == 1) return 1;
    400         return 0;
    401     }
    402     
    403     if (dp[bit][c_less][a_less][need] != -1) {
    404         return dp[bit][c_less][a_less][need];
    405     }
    406     
    407     long long ans = 0;
    408     int n_bit = (n >> bit) & 1;
    409     
    410     for (int a_bit = 0; a_bit <= 1; a_bit++) {
    411         for (int c_bit = 0; c_bit <= 1; c_bit++) {
    412             // Check constraint against n
    413             if (c_less && c_bit > n_bit) continue;
    414             
    415             // Check constraint a <= c (since we need a < c eventually)
    416             if (!a_less && a_bit > c_bit) continue;
    417             
    418             // Check the "need" condition for (a & c)
    419             if (need == 1 && (a_bit & c_bit) == 0) continue;
    420             if (need == 0 && (a_bit & c_bit) == 1) continue;
    421             
    422             int next_c_less = c_less && (c_bit == n_bit);
    423             int next_a_less = a_less || (a_bit < c_bit);
    424             int next_need = a_bit ^ c_bit; // The next bit's & must match this bit's ^
    425             
    426             ans = (ans + solve_dp(bit - 1, next_c_less, next_a_less, next_need)) % MOD;
    427         }
    428     }
    429     
    430     return dp[bit][c_less][a_less][need] = ans;
    431 }
    432  
    433 void solve() {
    434     cin >> n;
    435     memset(dp, -1, sizeof(dp));
    436     // Start at bit 60, c is constrained by n, a is not yet less than c, need = 0
    437     cout << solve_dp(60, 1, 0, 0) << "\n";
    438 }
    439  
    440 int main() {
    441     ios_base::sync_with_stdio(false);
    442     cin.tie(NULL);
    443     int t; cin >> t;
    444     while(t--) {
    445         solve();
    446     }
    447     return 0;
    448 }
    449 ```
    450 
    451 ---
    452 
    453 #### [2252F - Spectral Components](/contest/2252/problem/F "Codeforces Round 1115 (Div. 2)")
    454 
    455 **Solution**
    456 
    457 Let's solve the problem independently for a single color $c$ with $M$ vertices.
    458 
    459 First, consider the case where $k = 1$. The optimal component is a single vertex, which mathematically corresponds to the **centroid** of the $M$ vertices. For any edge $e$ in the tree, let $m_{\mathrm{in}}[e]$ and $m_{\mathrm{out}}[e]$ be the number of color $c$ vertices on either side of the edge. The number of paths from color $c$ vertices that must cross edge $e$ to reach the centroid is exactly $w[e] = \min(m_{\mathrm{in}}[e], m_{\mathrm{out}}[e])$. Thus, the total distance to the centroid is:
    460 
    461 $D(\mathrm{centroid}) = \sum w[e]$
    462 
    463 where the sum is over all edges $e$ in the tree.
    464 
    465 When $k \gt 1$, we must choose a connected component $S$ of $k$ vertices (which contains exactly $k - 1$ edges). Notice that if an edge $e$ is entirely inside $S$, no path from any colored vertex to $S$ needs to cross it (the distance is absorbed into the component). If an edge is outside $S$, exactly $w[e]$ paths still cross it. Thus, the cost of any valid component $S$ containing the centroid is:
    466 
    467 $\mathrm{Cost}(S) = D(\mathrm{centroid}) - \sum_{e \in S} w[e]$
    468 
    469 To minimize $\mathrm{Cost}(S)$, we must **maximize** the sum of $w[e]$ for the $k - 1$ edges we pick. A crucial property of tree centroids is that $w[e]$ is monotonically decreasing as you move away from the centroid. Because of this monotonicity, if we simply greedily pick the $k - 1$ edges with the globally maximum $w[e]$ values in the entire tree, they are mathematically guaranteed to form a connected component containing the centroid!
    470 
    471 However, calculating this naively for all colors takes $\mathcal{O}(N^2)$. To achieve the required time complexity, we process all colors using **Virtual Trees** (also known as Auxiliary Trees):
    472 
    473 1. For each color $c$, build a Virtual Tree of its $M$ vertices in $\mathcal{O}(M \log M)$ time using LCA.
    474 2. Run a bottom-up DP on the Virtual Tree to find $m_{\mathrm{in}}$ for each virtual subtree.
    475 3. A virtual edge $(u, v)$ represents a compressed path of $L = \operatorname{depth}[v] - \operatorname{depth}[u]$ real edges. Because there are no other vertices of color $c$ branching off this path, every single real edge on this path shares the exact same weight: $w' = \min(m_{\mathrm{in}}, m_c - m_{\mathrm{in}})$.
    476 4. For color $c$, collect the pairs (weight = $w'$, count = $L$) for all virtual edges.
    477 5. Sort these pairs by weight descending, and greedily pick up to $K - 1$ edges to subtract from the total sum of all $w[e]$.
    478 
    479 Since the sum of sizes of all Virtual Trees over all colors is $\mathcal{O}(n)$, the overall time complexity is $\mathcal{O}(n \log n)$.
    480 
    481 **Code (C++)**
    482 
    483 ```
    484 #include <iostream>
    485 #include <vector>
    486 #include <algorithm>
    487  
    488 using namespace std;
    489  
    490 const int LOG = 19;
    491 int n;
    492 vector<int> C, K;
    493 vector<vector<int>> adj;
    494 vector<int> tin, tout, depth;
    495 vector<vector<int>> up;
    496 int timer = 0;
    497  
    498 void dfs(int v, int p, int d) {
    499     tin[v] = ++timer;
    500     depth[v] = d;
    501     up[v][0] = p;
    502     for (int i = 1; i < LOG; i++) {
    503         up[v][i] = up[up[v][i - 1]][i - 1];
    504     }
    505     for (int u : adj[v]) {
    506         if (u != p) dfs(u, v, d + 1);
    507     }
    508     tout[v] = ++timer;
    509 }
    510  
    511 bool is_ancestor(int u, int v) {
    512     return tin[u] <= tin[v] && tout[u] >= tout[v];
    513 }
    514  
    515 int get_lca(int u, int v) {
    516     if (is_ancestor(u, v)) return u;
    517     if (is_ancestor(v, u)) return v;
    518     for (int i = LOG - 1; i >= 0; i--) {
    519         if (!is_ancestor(up[u][i], v)) u = up[u][i];
    520     }
    521     return up[u][0];
    522 }
    523  
    524 void solve() {
    525     cin >> n;
    526     C.assign(n + 1, 0);
    527     K.assign(n + 1, 0);
    528     adj.assign(n + 1, vector<int>());
    529     tin.assign(n + 1, 0);
    530     tout.assign(n + 1, 0);
    531     depth.assign(n + 1, 0);
    532     up.assign(n + 1, vector<int>(LOG, 1));
    533     timer = 0;
    534  
    535     vector<vector<int>> colors(n + 1);
    536     for (int i = 1; i <= n; i++) {
    537         cin >> C[i];
    538         colors[C[i]].push_back(i);
    539     }
    540     for (int i = 1; i <= n; i++) cin >> K[i];
    541     
    542     for (int i = 0; i < n - 1; i++) {
    543         int u, v;
    544         cin >> u >> v;
    545         adj[u].push_back(v);
    546         adj[v].push_back(u);
    547     }
    548  
    549     dfs(1, 1, 0);
    550     
    551     vector<long long> ans(n + 1, -1);
    552     vector<int> cnt(n + 1, 0);
    553  
    554     for (int c = 1; c <= n; c++) {
    555         if (colors[c].empty()) continue;
    556         
    557         int M_c = colors[c].size();
    558         int K_c = K[c];
    559  
    560         vector<int> nodes = colors[c];
    561         sort(nodes.begin(), nodes.end(), [](int a, int b) { return tin[a] < tin[b]; });
    562  
    563         int sz = nodes.size();
    564         for (int i = 0; i < sz - 1; i++) {
    565             nodes.push_back(get_lca(nodes[i], nodes[i+1]));
    566         }
    567         
    568         sort(nodes.begin(), nodes.end(), [](int a, int b) { return tin[a] < tin[b]; });
    569         nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
    570  
    571         for (int u : colors[c]) cnt[u] = 1;
    572  
    573         vector<int> st;
    574         vector<pair<int, int>> vt_edges;
    575         for (int u : nodes) {
    576             while (!st.empty() && !is_ancestor(st.back(), u)) st.pop_back();
    577             if (!st.empty()) vt_edges.push_back({st.back(), u});
    578             st.push_back(u);
    579         }
    580  
    581         long long total_dist = 0;
    582         vector<pair<long long, long long>> edge_weights; // {weight, count}
    583         
    584         for (int i = (int)vt_edges.size() - 1; i >= 0; i--) {
    585             int p = vt_edges[i].first;
    586             int u = vt_edges[i].second;
    587             cnt[p] += cnt[u];
    588             
    589             long long w = min((long long)cnt[u], (long long)M_c - cnt[u]);
    590             long long L = depth[u] - depth[p];
    591             total_dist += w * L;
    592             edge_weights.push_back({w, L});
    593         }
    594         
    595         sort(edge_weights.rbegin(), edge_weights.rend());
    596         
    597         long long saved = 0;
    598         long long needed = K_c - 1;
    599         for (auto& ew : edge_weights) {
    600             long long take = min(needed, ew.second);
    601             saved += take * ew.first;
    602             needed -= take;
    603             if (needed == 0) break;
    604         }
    605         
    606         ans[c] = total_dist - saved;
    607         for (int u : nodes) cnt[u] = 0;
    608     }
    609  
    610     for (int i = 1; i <= n; i++) {
    611         cout << ans[i] << (i == n ? "" : " ");
    612     }
    613     cout << "\n";
    614 }
    615  
    616 int main() {
    617     ios_base::sync_with_stdio(false);
    618     cin.tie(NULL);
    619     int t; cin >> t;
    620     while(t--) {
    621         solve();
    622     }
    623     return 0;
    624 }
    625 ```