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!