codeforces-scrape

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

1935.md (25852B)


      1 Source: https://codeforces.com/blog/entry/126662
      2 
      3 [1935A - Entertainment in MAC](/contest/1935/problem/A "Codeforces Round 932 (Div. 2)")
      4 
      5 Idea: [artew](/profile/artew "Expert artew")   
      6  Preparation: [artew](/profile/artew "Expert artew")   
      7  Editorial: [artew](/profile/artew "Expert artew")
      8 
      9 **Hints**
     10 
     11 **Hint 1**
     12 
     13 The answer will always have either the prefix $s$, or the reversed string $s$.
     14 
     15 **Hint 2**
     16 
     17 Adding the string to the end is required no more than once.
     18 
     19 **Solution**
     20 
     21 Let $t$ be the reversed string $s$. Notice that it is advantageous for us to use operation 1 (adding the reversed string at the end) no more than once. Indeed, having obtained some string, we will simply spend the remaining operations on flipping the string. Thus, we will get the original string or the reversed one, depending on the parity of the number of remaining operations.
     22 
     23 It is easy to see that the answer will always have either the prefix $s$, or $t$. Then, we find two lexicographically minimal strings with the prefix $s$ and $t$. These will be strings:
     24 
     25 $s$, flip the string $n$ times (since $n$ is even, every 2 operations we return the string to its original) $t + s$, initially flip the string, add the reversed string to the end, then flip the string $n - 2$ times. The answer will be the lexicographically minimal string out of $s$ and $t + s$.
     26 
     27 **Implementation on C++**
     28 
     29 ```
     30 #include <bits/stdc++.h>
     31 
     32 int main() {
     33     std::ios_base::sync_with_stdio(false);
     34     std::cin.tie(nullptr);
     35 
     36     int tt;
     37     std::cin >> tt;
     38     while (tt--) {
     39         int n;
     40         std::cin >> n;
     41         std::string s;
     42         std::cin >> s;
     43         std::string t = s;
     44         reverse(t.begin(), t.end());
     45         std::cout << std::min(s, t + s) << "\n";
     46     }
     47 
     48     return 0;
     49 }
     50 ```
     51 
     52 **Implementation on Python**
     53 
     54 ```
     55 t = int(input())
     56 for _ in range(t):
     57     n = int(input())
     58     s = input()
     59     t = s[::-1]
     60     print(min(s, t + s))
     61 ```
     62 
     63 [1935B - Informatics in MAC](/contest/1935/problem/B "Codeforces Round 932 (Div. 2)")
     64 
     65 Idea: [AndreyPavlov](/profile/AndreyPavlov "Candidate Master AndreyPavlov")   
     66  Preparation: [AndreyPavlov](/profile/AndreyPavlov "Candidate Master AndreyPavlov"), [artew](/profile/artew "Expert artew")   
     67  Editorial: [AndreyPavlov](/profile/AndreyPavlov "Candidate Master AndreyPavlov")
     68 
     69 **Hints**
     70 
     71 **Hint 1**
     72 
     73 What is the minimum $k$ that can be in a division?
     74 
     75 **Hint 2**
     76 
     77 Suppose $\operatorname{MEX}(x, y) = \operatorname{MEX}(y + 1, z)$, what can be said about $\operatorname{MEX}(x, z)$?
     78 
     79 **Tutorial**
     80 
     81 Suppose we correctly divided the array into $k \gt 2$ segments — $(1, r_1), (l_2, r_2), \ldots, (l_k, r_k)$. Then, note that we can merge first two subsegments, as the numbers from 0 to $mex - 1$ are encountered in these two segments and the number $mex$ is not encountered in them. Therefore, if there is a division into $k \gt 2$ segments, then there is also for $k - 1$ segments.
     82 
     83 Therefore, it is sufficient to check whether there is a division of the array into $k = 2$ segments, which can be done in $O(n)$ by precalcing $\operatorname{MEX}$ on the prefixes and suffixes, then we need to find some $i$ for which $\operatorname{MEX}(1, i) = \operatorname{MEX}(i + 1, n)$.
     84 
     85 **Implementation on C++**
     86 
     87 ```
     88 /* Includes */
     89 #include <bits/stdc++.h>
     90  
     91 /* Using libraries */
     92 using namespace std;
     93 
     94 /* Defines */
     95 #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
     96 #define vc vector
     97 #define pii pair <int, int>
     98 #define int long long
     99  
    100 void solve () {
    101     int n;
    102     cin >> n;
    103     vc <int> a(n);
    104     vc <int> cnt1(n + 1), cnt2(n + 1);
    105     for (int i = 0; i < n; ++i) {
    106         cin >> a[i];
    107         cnt2[a[i]]++;
    108     }
    109     int mex1 = 0, mex2 = 0;
    110     while (cnt2[mex2])
    111         ++mex2;
    112     for (int i = 0; i < n; ++i) {
    113         cnt1[a[i]]++;
    114         if (--cnt2[a[i]] == 0 && mex2 > a[i]) {
    115             mex2 = a[i];
    116         }
    117         while (mex2 && !cnt2[mex2 - 1])
    118             --mex2;
    119         while (cnt1[mex1])
    120             ++mex1;
    121         if (mex1 == mex2) {
    122             cout << "2\n";
    123             cout << 1 << " " << i + 1 << "\n";
    124             cout << i + 2 << " " << n << "\n";
    125             return;
    126         }
    127     }
    128     cout << "-1\n";
    129 }
    130 
    131 signed main() {
    132     fast;
    133     int t;
    134     cin >> t;
    135     while (t--) {
    136         solve();
    137     }
    138     return 0;
    139 }
    140 ```
    141 
    142 **Implementation on Python**
    143 
    144 ```
    145 def solve():
    146     n = int(input())
    147     a = list(map(int, input().split()))
    148     cur_mex = 0
    149     cur_have = [0] * (n + 1)
    150     for el in a:
    151         cur_have[el] += 1
    152     while cur_have[cur_mex]:
    153         cur_mex += 1
    154 
    155     another_mex = 0
    156     another_have = [0] * (n + 1)
    157     for i in range(n):
    158         cur_have[a[i]] -= 1
    159         if cur_have[a[i]] == 0 and cur_mex > a[i]:
    160             cur_mex = a[i]
    161 
    162         another_have[a[i]] += 1
    163         while another_have[another_mex]:
    164             another_mex += 1
    165 
    166         if cur_mex == another_mex:
    167             print(2)
    168             print("1 " + str(i + 1))
    169             print(str(i + 2) + " " + str(n))
    170             return
    171 
    172     print(-1)
    173 
    174 t = int(input())
    175 for _ in range(t):
    176     solve()
    177 ```
    178 
    179 [1935C - Messenger in MAC](/contest/1935/problem/C "Codeforces Round 932 (Div. 2)")
    180 
    181 Idea: [artew](/profile/artew "Expert artew")   
    182  Preparation: [artew](/profile/artew "Expert artew")   
    183  Editorial: [artew](/profile/artew "Expert artew")
    184 
    185 **Hints**
    186 
    187 **Hint 1**
    188 
    189 Try to find the answer to the problem by hand. How can changing the order of the messages reduce time?
    190 
    191 **Hint 2**
    192 
    193 Let the order in the response be $p_1, p_2, \ldots, p_k$. It is always advantageous for the response to satisfy $b_{p_1} \leq b_{p_2} \leq \ldots \leq b_{p_k}$.
    194 
    195 **Hint 3**
    196 
    197 Greedy?
    198 
    199 **Solution**
    200 
    201 Let the order in the response be $p_1, p_2, \ldots, p_k$. Note that in the optimal response, it will hold that $b_{p_1} \leq b_{p_2} \leq \ldots \leq b_{p_k}$. It's not hard to prove that such an order minimizes the sum of the absolute differences of adjacent elements in the array $b$. Then, this sum will turn into $b_{p_k} - b_{p_1}$, that is, the difference between the highest and lowest value of $b$ in the set of messages.
    202 
    203 Let's sort the pairs $(a_i, b_i)$ in ascending order of $b_i$. Fix the minimum value in the set of messages $b_l$ and the maximum value $b_r$. Note that the sum of the absolute differences of $b$ in the response will not change if taking values $b_l \leq b_i \leq b_r$. Thus, the task reduces to finding the maximum number of messages so that $\sum a \leq L - (b_r - b_l)$.
    204 
    205 Iterate over $b_l$ and $b_r$. Apply a greedy algorithm, sort all values of $a_i$ ($l \leq i \leq r$), and keep adding values until the time exceeds $L$. This solution works in $O(n^3\log{}n)$, which is too slow.
    206 
    207 To speed up the solution, while iterating over $b_r$, maintain a data structure that allows adding an element, removing the maximum, getting the maximum (in C++, there are $\textit{multiset}$ and $\textit{priority_queue}$). In this data structure, maintain the minimum values of $a$, so the sum of times does not exceed $L$. Then, if the current time exceeds $L$, remove from the structure until the current time becomes no more than $L$. There will be no more than $n$ such removals. We have obtained a solution in $O(n^2\log{}n)$, which is feasibly fast.
    208 
    209 **Implementation on C++**
    210 
    211 ```
    212 #include <bits/stdc++.h>
    213 
    214 signed main() {
    215     std::ios_base::sync_with_stdio(false);
    216     std::cin.tie(nullptr);
    217 
    218     int t = 1;
    219     std::cin >> t;
    220     while (t--) {
    221         int n, L;
    222         std::cin >> n >> L;
    223         std::vector<std::pair<int, int>> v(n);
    224         for (int i = 0 ; i < n ; i++) {
    225             std::cin >> v[i].second >> v[i].first;
    226         }
    227         std::sort(v.begin(), v.end());
    228 
    229         int ans = 0;
    230         for (int l = 0 ; l < n ; l++) {
    231             std::multiset<int> s;
    232             int cur = 0;
    233             for (int r = l ; r < n ; r++) {
    234                 s.insert(v[r].second);
    235                 cur += v[r].second;
    236                 while (!s.empty() && v[r].first - v[l].first + cur > L) {
    237                     int max_value = *s.rbegin();
    238                     cur -= max_value;
    239                     s.extract(max_value);
    240                 }
    241                 ans = std::max(ans, (int) s.size());
    242             }
    243         }
    244 
    245         std::cout << ans << "\n";
    246     }
    247 
    248     return 0;
    249 }
    250 ```
    251 
    252 **Implementation on Python**
    253 
    254 ```
    255 import heapq
    256 import sys
    257 
    258 input = sys.stdin.readline
    259 
    260 t = int(input())
    261 for _ in range(t):
    262     n, L = map(int, input().split())
    263     v = []
    264     for i in range(n):
    265         a, b = map(int, input().split())
    266         v.append((b, a))
    267     v.sort()
    268 
    269     ans = 0
    270     for l in range(n):
    271         pq = []
    272         heapq.heapify(pq)
    273         cur = 0
    274         size = 0
    275         for r in range(l, n):
    276             heapq.heappush(pq, -v[r][1])
    277             size += 1
    278             cur += v[r][1]
    279             while size and v[r][0] - v[l][0] + cur > L:
    280                 maxx = -heapq.heappop(pq)
    281                 cur -= maxx
    282                 size -= 1
    283             ans = max(ans, size)
    284 
    285     print(ans)
    286 ```
    287 
    288 [1935D - Exam in MAC](/contest/1935/problem/D "Codeforces Round 932 (Div. 2)")
    289 
    290 Idea: [IzhitskiyTimofey](/profile/IzhitskiyTimofey "Master IzhitskiyTimofey")   
    291  Preparation: [IzhitskiyTimofey](/profile/IzhitskiyTimofey "Master IzhitskiyTimofey")   
    292  Editorial: [IzhitskiyTimofey](/profile/IzhitskiyTimofey "Master IzhitskiyTimofey")
    293 
    294 **Hints**
    295 
    296 **Hint 1**
    297 
    298 The principle of inclusion-exclusion.
    299 
    300 **Hint 2**
    301 
    302 The equation $x+y = s_i$, $y-x=s_j$ has $0$ or $1$ solutions with integers $x, y$.
    303 
    304 **Tutorial**
    305 
    306 Applying the formula of inclusion-exclusion, the answer to the problem will be: $\mathrm{cnt}(x, y) - \mathrm{cnt}(x, y: x + y \in s) - \mathrm{cnt}(x, y: y - x \in s) + \mathrm{cnt}(x, y: x + y, y - x \in s)$. Let's calculate each value separately.
    307 
    308 The number of possible pairs $x, y$ is $\frac{(c+1)\cdot(c+2)}{2}$.
    309 
    310 The number of pairs $x, y: x + y \in s$. We iterate over the sum value $s_i$, let $x + y = s_i$, then for $0 \leq x \leq \lfloor \frac{s_i}{2} \rfloor$ there will correspond exactly one $y$, i.e., the number of pairs with such a sum is $\lfloor \frac{s_i}{2} \rfloor + 1$.
    311 
    312 The number of pairs $x, y: y - x \in s$. We iterate over the difference value $s_i$, let $y - x = s_i$, then for $s_i \leq y \leq c$ there will correspond exactly one $x$, i.e., the number of pairs with such a difference is $c - s_i + 1$.
    313 
    314 The number of pairs $x, y: x + y, y - x \in s$. Let $x+y=s_i$, $y-x=s_j$, then $x = \frac{s_i - s_j}{2}$, and $y = \frac{s_i+s_j}{2}$. If $s_i, s_j$ have different parities, then such $x, y$ will not be suitable because they will be non-integers; otherwise, such $x, y$ are suitable, and we need to add this pair. Then, let's calculate the number of even and odd numbers in $s$ — $even$ and $odd$ respectively. Thus, the number of such pairs is $\frac{even\cdot(even+1)}{2}+\frac{odd\cdot(odd+1)}{2}$.
    315 
    316 With all these quantities, we can calculate the answer. The final complexity is $O(n)$. The problem can also be solved in $O(n \cdot \log n)$ or $O(n)$ using other methods.
    317 
    318 **Implementation on C++**
    319 
    320 ```
    321 #include <bits/stdc++.h>
    322 
    323 using namespace std;
    324 using ll = long long;
    325 
    326 void solve_case() {
    327     int n, c;
    328     cin >> n >> c;
    329     vector<int> s(n);
    330     for (int i = 0; i < n; i++) cin >> s[i];
    331     int odd = 0, even = 0;
    332     ll ans = 1ll * (c + 1) * (c + 2) / 2;
    333     for (int i = 0; i < n; i++) {
    334         ans -= s[i] / 2 + 1;
    335         ans -= c - s[i] + 1;
    336         if (s[i] % 2 == 0) {
    337             even++;
    338         } else {
    339             odd++;
    340         }
    341     }
    342     ans += 1ll * even * (even + 1) / 2;
    343     ans += 1ll * odd * (odd + 1) / 2;
    344     cout << ans << "\n";
    345 }
    346 
    347 int main() {
    348     ios::sync_with_stdio(false);
    349     cin.tie(0), cout.tie(0);
    350     int T = 1;
    351     cin >> T;
    352     while (T--) {
    353         solve_case();
    354     }
    355 }
    356 ```
    357 
    358 **Implementation on Python**
    359 
    360 ```
    361 def solve_case() :
    362     n, c = map(int, input().split())
    363     s = list(map(int, input().split()))
    364     ans = (c + 1) * (c + 2) // 2
    365     even, odd = 0, 0
    366     for i in range(n):
    367         ans -= s[i] // 2 + 1
    368         ans -= c - s[i] + 1
    369         if s[i] % 2 == 0:
    370             even += 1
    371         else:
    372             odd += 1
    373     ans += even * (even + 1) // 2
    374     ans += odd * (odd + 1) // 2
    375     print(ans)
    376 
    377 t = int(input())
    378 for test in range(t):
    379     solve_case()
    380 ```
    381 
    382 [1935E - Distance Learning Courses in MAC](/contest/1935/problem/E "Codeforces Round 932 (Div. 2)")
    383 
    384 Idea: [IzhitskiyTimofey](/profile/IzhitskiyTimofey "Master IzhitskiyTimofey")   
    385  Preparation: [AndreyPavlov](/profile/AndreyPavlov "Candidate Master AndreyPavlov")   
    386  Editorial: [AndreyPavlov](/profile/AndreyPavlov "Candidate Master AndreyPavlov")
    387 
    388 **Hints**
    389 
    390 **Hint 1**
    391 
    392 Try to solve the problem if $x_i = 0$ for each $i$.
    393 
    394 **Hint 2**
    395 
    396 What will be the answer for two segments $(0, 2^i), (0, 2^i)$?
    397 
    398 **Hint 3**
    399 
    400 Which bits will definitely be included in the answer?
    401 
    402 **Tutorial**
    403 
    404 Let's solve the problem when $x = 0$. Then we will iterate over the bits from the most significant to the least significant and try to include them in the answer. Suppose we are iterating over bit $i$, then if such a bit occurs $c$ times in $y$ numbers there are several cases:
    405 
    406 * $c = 0$ — this bit cannot be included in the answer
    407 * $c = 1$ — this bit will be included in the answer, we add it
    408 * $c \gt 1$ — a special case, because for one number where bit x is present, we can set it, and for another number, we can set all bits $j \lt i$.
    409 
    410 Therefore, if we encounter some bit $i$ that occurs more than once, then all bits $j \le i$ will also be included in the answer. Now let's solve the original problem, for this we take a pair $(x_i, y_i)$ and find the bitwise largest common prefix — let it be number $w$. Then it is clear that all bits from $w$ will be included in the answer, then we make a new pair $(x'_i, y'_i)$ = $(x_i - w, y_i - w)$, and remember the number $w_i$. Now note that the number $y'_i - 1 \ge x'_i$. Why do we need this fact? Remember, in the case when some bit occurred more than once, we added it and all smaller bits to the answer. For this, we would set at this position a number equal to $2^i - 1$ (and other larger bits $i$), but if $y'_i - 1 \ge x'_i$, then we can always add all such bits.
    411 
    412 Therefore, the solution algorithm for request $j$ is as follows:
    413 
    414 * Take the Bitwise OR of all $w_i$ for $l_j \le i \le r_j$, let this be number $W$
    415 * Iterate over bit $i$ and similarly to the case $x = 0$ consider the same cases, but for the array $y'$. Also, take into account that the bit occurs in $W$.
    416 
    417 This solution can be implemented in $O(n \cdot \log n)$ using prefix sums for each bit. There is also a solution using a segment tree, so the problem can be solved with modification requests as well.
    418 
    419 **Implementation on C++**
    420 
    421 ```
    422 /* Includes */
    423 #include <bits/stdc++.h>
    424 #include <ext/pb_ds/tree_policy.hpp>
    425  
    426 /* Using libraries */
    427 using namespace std;
    428  
    429 /* Defines */
    430 template <class T>
    431 using vc = vector <T>;
    432 using ll = long long;
    433 using ld = long double;
    434 using pii = pair <int, int>;
    435  
    436 template<class T>
    437 void output(T &a) {
    438     for (auto i : a)
    439         cout << i << ' ';
    440     cout << '\n';
    441 }
    442  
    443 template<class T>
    444 bool chmin(T &a, T b) {
    445     if (a > b) {
    446         a = b;
    447         return true;
    448     }
    449     return false;
    450 }
    451  
    452 template<class T>
    453 bool chmax(T &a, T b) {
    454     if (a < b) {
    455         a = b;
    456         return true;
    457     }
    458     return false;
    459 }
    460  
    461 const int N = 2e5;
    462 const int bit = 30;
    463  
    464 struct segtree {
    465     vc <int> t; int n;
    466     segtree (int n) : n(n) {
    467         t.resize(n * 2);
    468     }
    469     void upd (int i, int x) {
    470         for (t[i += n] = x; i > 1; i >>= 1) {
    471             t[i >> 1] = t[i] | t[i ^ 1];
    472         }
    473     }
    474     int get (int l, int r) {
    475         int res = 0;
    476         for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    477             if (l & 1)
    478                 res |= t[l++];
    479             if (r & 1)
    480                 res |= t[--r];
    481         }
    482         return res;
    483     }
    484 };
    485  
    486 int n;
    487 int l[N], r[N];
    488 int w[N];
    489 void fix () {
    490     for (int i = 0; i < n; ++i) {
    491         if (l[i] == r[i]) {
    492             w[i] = l[i];
    493             l[i] = r[i] = 0;
    494             continue;
    495         }
    496         int pref = (1 << (__lg(l[i] ^ r[i]) + 1)) - 1;
    497         w[i] = r[i] - (r[i] & pref);
    498         r[i] &= pref;
    499         l[i] &= pref;
    500     }
    501 }
    502  
    503 void solve() {
    504     cin >> n;
    505     for (int i = 0; i < n; ++i) {
    506         cin >> l[i] >> r[i];
    507     }
    508     fix();
    509     segtree t(n);
    510     vc <vc <int>> bits(bit, vc <int> (n + 1));
    511     for (int i = 0; i < n; ++i) {
    512         t.upd(i, w[i]);
    513         for (int j = 0; j < bit; ++j) {
    514             bits[j][i + 1] = bits[j][i];
    515             if (r[i] >> j & 1) {
    516                 bits[j][i + 1]++;
    517             }
    518         }
    519     }
    520     int q;
    521     cin >> q;
    522     while (q--) {
    523         int x, y;
    524         cin >> x >> y; --x;
    525         int ans = t.get(x, y);
    526         for (int j = bit - 1; j >= 0; --j) {
    527             int cnt = bits[j][y] - bits[j][x] + (ans >> j & 1);
    528             if (cnt > 1) {
    529                 ans |= (2 << j) - 1;
    530                 break;
    531             } else if (cnt == 1) {
    532                 ans |= 1 << j;
    533             }
    534         }
    535         cout << ans << ' ';
    536     }
    537     cout << "\n";
    538 }
    539  
    540 signed main() {
    541     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    542     int t = 1;
    543     cin >> t;
    544     while (t--) {
    545         solve();
    546     }
    547 }
    548 ```
    549 
    550 [1935F - Andrey's Tree](/contest/1935/problem/F "Codeforces Round 932 (Div. 2)")
    551 
    552 Idea: [AndreyPavlov](/profile/AndreyPavlov "Candidate Master AndreyPavlov")   
    553  Preparation: [IzhitskiyTimofey](/profile/IzhitskiyTimofey "Master IzhitskiyTimofey")   
    554  Editorial: [IzhitskiyTimofey](/profile/IzhitskiyTimofey "Master IzhitskiyTimofey")
    555 
    556 **Hints**
    557 
    558 **Hint 1**
    559 
    560 What different values can the answer for a vertex take?
    561 
    562 **Hint 2**
    563 
    564 Edges with a weight of 1 can connect all vertices $[1, v - 1]$ and all vertices $[v + 1, n]$.
    565 
    566 **Hint 3**
    567 
    568 Consider the edges of the form $(mn_u, mn_u - 1)$, $(mx_u, mx_u + 1)$, where $mn_u$, $mx_u$ are the minimum and maximum in the subtree of vertex u with respect to $v$.
    569 
    570 **Tutorial**
    571 
    572 Let's fix some vertex $v$ for which the answer is being calculated. Suppose the degree of the vertex $v$ in the tree is $deg_v$, then it's clear that it's necessary to add $deg_v - 1$ edges. Consider the components that appear after removing $v$. Then, the goal is to use the new edges to unite all the components into one, using the minimum total cost. This is the same as finding the minimum spanning tree in a graph, where the vertices are the components that resulted from removing $v$, and for every $a, b$, an edge with a weight of $|a - b|$ is drawn between the components containing $a$ and $b$.
    573 
    574 Let's simulate Kruskal's algorithm for this graph. Consider all the single-weight edges in this graph: $(1, 2), (2, 3), ..., (v - 2, v - 1), (v + 1, v + 2), ..., (n - 1, n)$. It's clear that using the single-weight edges, the vertices with numbers $[1, v - 1]$ will definitely end up in one component, and the vertices with numbers $[v + 1, n]$ will also end up in one component. To unite these two components, it would be optimal to add an edge $(v - 1, v + 1)$.
    575 
    576 It turns out that it's sufficient to consider only all the single-weight edges and the edge $(v - 1, v + 1)$. Let's limit the number of single-weight edges to $O(deg_v)$. For this, in each component $u$, calculate $mn_u$ and $mx_u$ — the minimum and maximum in the component, respectively. Claim: among the single-weight edges, it's sufficient to consider edges of the form $(mn_u, mn_u - 1)$, $(mx_u, mx_u + 1)$.
    577 
    578 **Proof**
    579 
    580 First, understand when it's necessary to add the edge $(v - 1, v + 1)$. Note that if there's at least one component $u$ such that $mn_u \lt v \lt mx_u$, then the edge $(v - 1, v + 1)$ won't be needed; otherwise, it will be. This is quite easy to show by simulating Kruskal's algorithm.
    581 
    582 Let $v = 1$. We'll show that using edges $(mn_u, mn_u - 1)$, all components will unite. Go through the vertices $x$ from $2$ to $n$ and maintain the invariant that all vertices from $2$ to $x$ are in one component. At $x = 2$, this holds. When $x$ is the minimum in some component, then the edge $(x - 1, x)$ will be added, and since $x - 1$ is in one component with $2$, $x$ will now also be. When $x$ is not the minimum in some component, then $mn$ — the minimum in the component $x$ will be in one component with $2$ ($mn \lt x$, the invariant holds), meaning $x$ will also be in one component with $2$. Thus, it turns out that all will be in one component.
    583 
    584 Now consider an arbitrary $v$. Separately consider the prefix of vertices $[1, v - 1]$ and the suffix $[v + 1, n]$. Then, similarly to $v = 1$, it can be shown that for the prefix of vertices $[1, v - 1]$, using edges of the form $(mn_u, mn_u - 1)$, you can unite $[1, v - 1]$. Similarly, for the suffix of vertices $[v + 1, n]$, using edges of the form $(mx_u, mx_u + 1)$, you can unite $[v + 1, n]$.
    585 
    586 Now, if the edge $(v - 1, v + 1)$ is necessary, then add it to the answer. Otherwise, there's at least one component $u$ such that $mn_u \lt v \lt mx_u$, meaning the prefix of vertices $[1, v - 1]$ and the suffix $[v + 1, n]$ will unite into one component.
    587 
    588 Finding $mn_u$, $mx_u$ for each component is straightforward; what remains is to determine which components are connected by the edges $(mn_u, mn_u - 1)$, $(mx_u, mx_u + 1)$. This can be done with binary search through the Euler tour of the tree. After that, Kruskal's algorithm can be initiated to calculate the answer.
    589 
    590 Let's estimate the time complexity. For a specific vertex $v$, the time complexity will be $deg_v \cdot \log n$, so the total time complexity is $O(n \cdot \log n)$.
    591 
    592 Depending on the implementation of the last step, the problem can be solved in $O(n)$, $O(n \cdot \alpha(n))$, where $\alpha(n)$ is the inverse Ackermann function relative to $n$.
    593 
    594 **Implementation on C++**
    595 
    596 ```
    597 #include <bits/stdc++.h>
    598  
    599 using namespace std;
    600  
    601  
    602 struct DSU {
    603     vector<int> p, r;
    604     int comp;
    605     DSU(int n) : p(n), r(n) {
    606         iota(p.begin(), p.end(), 0);
    607         comp = n;
    608     }
    609     int find(int v) {
    610         return (p[v] == v) ? v : p[v] = find(p[v]);
    611     }
    612     bool join(int a, int b) {
    613         a = find(a), b = find(b);
    614         if (a == b) return false;
    615         comp--;
    616         if (r[a] < r[b]) swap(a, b);
    617         p[b] = a;
    618         if (r[a] == r[b]) r[a]++;
    619         return true;
    620     }
    621 };
    622  
    623 int main() {
    624     ios::sync_with_stdio(false);
    625     cin.tie(0), cout.tie(0);
    626     int T;
    627     cin >> T;
    628     while (T--) {
    629         int n;
    630         cin >> n;
    631         vector<vector<int>> g(n);
    632         for (int i = 0; i < n - 1; i++) {
    633             int x, y;
    634             cin >> x >> y;
    635             x--, y--;
    636             g[x].push_back(y);
    637             g[y].push_back(x);
    638         }
    639         vector<int> tin(n), tout(n), l0(n), r0(n);
    640         vector<int> lup(n), rup(n);
    641         int timer = 0;
    642         vector<int> ord;
    643         function<void(int, int)> dfs = [&](int v, int p) {
    644             l0[v] = r0[v] = v;
    645             tin[v] = timer++;
    646             ord.push_back(v);
    647             for (int u : g[v]) {
    648                 if (u == p) continue;
    649                 dfs(u, v);
    650                 l0[v] = min(l0[v], l0[u]);
    651                 r0[v] = max(r0[v], r0[u]);
    652             }
    653             tout[v] = timer - 1;
    654         };
    655         dfs(0, 0);
    656         function<bool(int, int)> ancestor = [&](int v, int u) {
    657             return tin[v] <= tin[u] && tin[u] <= tout[v];
    658         };
    659         vector<int> pref_min_ord(n + 1, n), suf_min_ord(n + 1, n);
    660         vector<int> pref_max_ord(n + 1, -1), suf_max_ord(n + 1, -1);
    661         for (int i = 0; i < n; i++) {
    662             pref_min_ord[i + 1] = min(pref_min_ord[i], ord[i]);
    663             pref_max_ord[i + 1] = max(pref_max_ord[i], ord[i]);
    664         }
    665         for (int i = n - 1; i >= 0; i--) {
    666             suf_min_ord[i] = min(suf_min_ord[i + 1], ord[i]);
    667             suf_max_ord[i] = max(suf_max_ord[i + 1], ord[i]);
    668         }
    669         for (int id = (int)ord.size() - 1; id >= 0; id--) {
    670             int v = ord[id];
    671             lup[v] = min(pref_min_ord[tin[v]], suf_min_ord[tout[v] + 1]);
    672             rup[v] = max(pref_max_ord[tin[v]], suf_max_ord[tout[v] + 1]);
    673         }
    674         vector<vector<pair<int, int>>> ans(n);
    675         vector<int> weight(n);
    676         function<void(int, int)> dfs2 = [&](int v, int p) {
    677             vector<int> all_id, all_tin;
    678             int idpar = -1;
    679             for (int id = 0; id < g[v].size(); id++) {
    680                 int u = g[v][id];
    681                 if (u != p) {
    682                     dfs2(u, v);
    683                     all_id.push_back(id);
    684                     all_tin.push_back(tin[u]);
    685                 } else {
    686                     idpar = id;
    687                 }
    688             }
    689             function<int(int)> get_subtree = [&](int u) {
    690                 if (!ancestor(v, u)) return idpar;
    691                 return all_id[upper_bound(all_tin.begin(), all_tin.end(), tin[u]) - all_tin.begin() - 1];
    692             };
    693             DSU dsu(g[v].size());
    694             function<void(int, int)> try_add = [&](int x, int y) {
    695                 if (x == -1 || y == n || x == v || y == v) return;
    696                 if (dsu.join(get_subtree(x), get_subtree(y))) {
    697                     ans[v].push_back({x, y});
    698                     weight[v] += abs(x - y);
    699                 }
    700             };
    701             for (int u : g[v]) {
    702                 if (u != p) {
    703                     try_add(l0[u] - 1, l0[u]);
    704                     try_add(r0[u], r0[u] + 1);
    705                 } else {
    706                     try_add(lup[v] - 1, lup[v]);
    707                     try_add(rup[v], rup[v] + 1);
    708                 }
    709             }
    710             if (dsu.comp != 1) {
    711                 try_add(v - 1, v + 1);
    712             }
    713             assert(dsu.comp == 1);
    714         };
    715         dfs2(0, 0);
    716         for (int i = 0; i < n; i++) {
    717             cout << weight[i] << " " << ans[i].size() << "\n";
    718             for (auto [a, b] : ans[i]) {
    719                 cout << a + 1 << " " << b + 1 << "\n";
    720             }
    721             cout << "\n";
    722         }
    723     }
    724 }
    725 ```
    726 
    727 We hope you liked our problems!