1396.md (20990B)
1 Source: https://codeforces.com/blog/entry/82142 2 3 We hoped you find our problems interesting. We apologize for the late editorial. Hopefully you were still able to enjoy our contest. 4 5 Anyway, here are the tutorials for each of the problems: 6 7 ### [1397A - Juggling Letters](/contest/1397/problem/A "Codeforces Round 666 (Div. 2)") 8 9 If the total number of occurrences of some character $c$ is not a multiple of $n$, then it is impossible to make all $n$ strings equal — because then it is impossible for all $n$ strings to have the same number of $c$. 10 11 On the other hand, if the total number of occurrences of every character $c$ is a multiple of $n$, then it is always possible to make all $n$ strings equal. To achieve this, for every character $c$ we move exactly ((the total number of occurrences of $c$) $/$ $n$) characters $c$ to the end of each string, and by the end we will have all $n$ strings equal each other. 12 13 We can easily check if the condition satisfies by counting the total number of occurrences of each character $c$ and check its divisibility by $n$. The final complexity is $O(S \cdot 26)$ or $O(S)$ where $S$ is the sum of lengths of all strings. 14 15 **C++ solution** 16 17 ``` 18 #include <iostream> 19 #include <vector> 20 21 using namespace std; 22 23 int main() 24 { 25 int tests; 26 cin >> tests; 27 while (tests--) { 28 int n; 29 cin >> n; 30 31 vector<int> cnt(26); 32 for (int i = 0; i < n; ++i) { 33 string s; 34 cin >> s; 35 for (char ch : s) { 36 ++cnt[ch - 'a']; 37 } 38 } 39 40 bool ans = true; 41 for (int i = 0; i < 26; ++i) { 42 if (cnt[i] % n != 0) { 43 ans = false; 44 break; 45 } 46 } 47 48 cout << (ans ? "YES" : "NO") << endl; 49 } 50 } 51 ``` 52 53 **Python solution** 54 55 ``` 56 numTests = int(input()) 57 for testNo in range(numTests): 58 n = int(input()) 59 cnt = [0 for i in range(26)] 60 for _ in range(n): 61 s = input() 62 for i in s: 63 cnt[ord(i) - 97] += 1 64 65 ans = True 66 for i in range(26): 67 if cnt[i] % n != 0: 68 ans = False 69 break 70 71 if ans: 72 print('YES') 73 else: 74 print('NO') 75 ``` 76 77 ### [1397B - Power Sequence](/contest/1397/problem/B "Codeforces Round 666 (Div. 2)") 78 79 First of all, the optimal way to reorder is to sort $a$ in non-decreasing order. 80 81 **Proof** 82 83 Note that the cost the transform $a_i$ to $c^i$ is $\lvert a_i - c^i \rvert$. While there is a pair $(a_i, a_j)$ such that $i \lt j$ and $a_i \gt a_j$, swap $a_i$ and $a_j$. Since $\lvert x \rvert + \lvert y \rvert = max \{ \lvert x + y \rvert, \lvert x - y \rvert \}$, we have 84 85 $\lvert a_i - c^i \rvert + \lvert a_j - c^j \rvert$ 86 87 $= max \{ \lvert (a_i + a_j) - (c^i + c^j) \rvert, \lvert (a_i - a_j) - (c^i - c^j) \rvert \}$ 88 89 $\ge max \{ \lvert (a_j + a_i) - (c^i + c^j) \rvert, \lvert (a_j - a_i) - (c^i - c^j) \rvert \}$ 90 91 $= \lvert a_j - c^i \rvert + \lvert a_i - c^j \rvert$ 92 93 when $a_i \gt a_j$ and $c^i \le c^j$, so the total cost does not increase. Hence, it is best to have $a_0 \le a_1 \le \cdots \le a_{n-1}$. 94 95 From now on, we assume $a$ is sorted in non-decreasing order. 96 97 Denote $a_{max} = a_{n - 1}$ as the maximum value in $a$, $f(x) = \sum{\lvert a_i - x^i \rvert}$ as the minimum cost to transform $a$ into ${x^0, x^1, \cdots, x^{n-1}}$, and $c$ as the value where $f(c)$ is minimum. 98 99 Note that $c^{n - 1} - a_{max} \le f(c) \le f(1)$, which implies $c^{n - 1} \le f(1) + a_{max}$. 100 101 We enumerate $x$ from $1, 2, 3, \dots$ until $x^{n - 1}$ exceeds $f(1) + a_{max}$, calculate $f(x)$ in $O(n)$, and the final answer is the minimum among all calculated values. The final complexity is $O(n \cdot max(x))$. 102 103 But why doesn't this get TLE? Because $f(1) = \sum{(a_i - 1)} \lt a_{max} \cdot n \le 10^9 \cdot n$, thus $x^{n - 1} \le f(1) + a_{max} \le 10^9 \cdot (n + 1)$. When $n = 3, 4, 5, 6$, $max(x)$ does not exceed $63245, 1709, 278, 93$ respectively; so we can see that $O(n \cdot max(x))$ comfortably fits in the time limit. 104 105 **C++ solution** 106 107 ``` 108 #include <iostream> 109 #include <vector> 110 #include <algorithm> 111 #include <numeric> 112 113 using namespace std; 114 115 const int64_t INF = 1e17; 116 inline int64_t mul(int64_t a, int64_t b) 117 { 118 return (INF / a > b ? a * b : INF); 119 } 120 121 inline int64_t add(int64_t a, int64_t b) 122 { 123 return (a + b >= INF ? INF : a + b); 124 } 125 126 int main() 127 { 128 int n; 129 cin >> n; 130 131 vector<int> a(n); 132 for (int &x : a) cin >> x; 133 sort(a.begin(), a.end()); 134 135 if (n <= 2) { 136 cout << a[0] - 1 << endl; 137 } else { 138 int64_t ans = accumulate(a.begin(), a.end(), 0ll) - n; 139 140 for (int x = 1; ; ++x) { 141 int64_t curPow = 1, curCost = 0; 142 for (int i = 0; i < n; ++i) { 143 curCost = add(curCost, abs(a[i] - curPow)); 144 curPow = mul(curPow, x); 145 } 146 147 if (curPow == INF || curPow / x > ans + a[n - 1]) break; 148 ans = min(ans, curCost); 149 } 150 151 cout << ans << endl; 152 } 153 } 154 ``` 155 156 **Python solution** 157 158 ``` 159 n = int(input()) 160 a = [int(x) for x in input().split()] 161 a.sort() 162 inf = 10**18 163 164 if n <= 2: 165 print(a[0] - 1) 166 else: 167 ans = sum(a) - n 168 169 for x in range(1, 10**9): 170 curPow = 1 171 curCost = 0 172 for i in range(n): 173 curCost += abs(a[i] - curPow) 174 curPow *= x 175 if curPow > inf: 176 break 177 178 if curPow > inf: 179 break 180 if curPow / x > ans + a[n - 1]: 181 break 182 183 ans = min(ans, curCost) 184 185 print(ans) 186 ``` 187 188 ### [1396A - Multiples of Length](/contest/1396/problem/A "Codeforces Round 666 (Div. 1)") 189 190 In this problem, the answer is rather simple. Here is one possible solution to this task. 191 192 **Solution for n = 1** 193 194 $1 \space \space 1$ 195 $0$ 196 $1 \space \space 1$ 197 $0$ 198 $1 \space \space 1$ 199 $-a_1$ 200 201 **Solution for n != 1** 202 203 $1 \space \space 1$ 204 $-a_1$ 205 $1 \space \space n$ 206 $0, \space -n \cdot a_2, \space -n \cdot a_3, \space \dots , \space -n \cdot a_n$ 207 $2 \space \space n$ 208 $(n-1) \cdot a_2, \space (n-1) \cdot a_3, \space \dots , \space (n-1) \cdot a_n$ 209 210 **C++ solution** 211 212 ``` 213 #include <bits/stdc++.h> 214 215 using namespace std; 216 217 using ll = long long; 218 219 int main() { 220 ios_base::sync_with_stdio(false); cin.tie(nullptr); 221 int N; 222 cin >> N; 223 vector<ll> A(N); 224 for (int i = 0; i < N; ++i) cin >> A[i]; 225 if (N == 1) { 226 for (int z = 0; z < 3; ++z) { 227 cout << "1 1\n"; 228 cout << -A[0] << "\n"; 229 A[0] = 0; 230 } 231 return 0; 232 } 233 cout << "1 " << N << "\n"; 234 for (int i = 0; i + 1 < N; ++i) cout << -A[i] * N << " "; cout << "0\n"; 235 cout << "1 " << N - 1 << "\n"; 236 for (int i = 0; i + 1 < N; ++i) cout << A[i] * (N - 1) << " "; cout << "\n"; 237 cout << N << " " << N << "\n"; 238 cout << -A[N - 1] << "\n"; 239 return 0; 240 } 241 ``` 242 243 **Python solution** 244 245 ``` 246 n = int(input()) 247 a = list(map(int, input().split())) 248 249 if n == 1: 250 print('1 1', -a[0], '1 1', '0', '1 1', '0', sep='\n') 251 exit(0) 252 253 print(1, n) 254 for i in range(n): 255 print(-a[i] * n, end = ' ') 256 a[i] -= a[i] * n 257 print() 258 259 print(1, n - 1) 260 for i in range(n - 1): 261 print(-a[i], end = ' ') 262 a[i] = 0 263 print() 264 265 print(2, n) 266 for i in range(1, n): 267 print(-a[i], end = ' ') 268 a[i] = 0 269 print() 270 ``` 271 272 ### [1396B - Stoned Game](/contest/1396/problem/B "Codeforces Round 666 (Div. 1)") 273 274 Let us denote $S$ as the current total number of stones. 275 276 Consider the following cases: 277 278 **Case A: There is a pile that has more than $\lfloor \frac{S}{2} \rfloor$ stones.** 279 280 The first player (T) can always choose from this pile, thus he (T) is the winner. 281 282 **Case B: Every pile has at most $\lfloor \frac{S}{2} \rfloor$ stones, and $S$ is even.** 283 284 It can be proven that the second player (HL) always wins. 285 286 **Proof 1** 287 288 Let us prove by induction: 289 290 When $S = 0$, the second player obviously wins. 291 292 When $S \geq 2$, consider the game state after the first player moves. If there is a pile that now has more than $\lfloor \frac{S}{2} \rfloor$ stones, then we arrive back at *case A* where the next player to move wins. Otherwise, the second player can choose from any valid pile (note that the case condition implies that there are at least two non-empty piles before the first player's move). Now $S$ has been reduced by $2$, and every pile still has at most $\lfloor \frac{S}{2} \rfloor$ stones. 293 294 **Proof 2** 295 296 The condition allows us to assign a perfect matching of stones, where one stone is matched with exactly one stone from a different pile. 297 298 A greedy way to create such a matching: Give each label $0, 1, \dots, S - 1$ to a different stone so that for every pair of stones with labels $l \lt r$ that are from the same pile, stones $l + 1, l + 2, \dots, r - 1$ are also from that pile; then match stones $i$ with $i + \frac{S}{2}$ for all $0 \le i \lt \frac{S}{2}$. 299 300 For every stone that the first player removes, the second player can always remove its matching stone, until the first player can no longer make a move and loses. 301 302 **Case C: Every pile has at most $\lfloor \frac{S}{2} \rfloor$ stones, and $S$ is odd.** 303 304 The first player (T) can choose from any pile, and we arrive back at *case B* where the next player to move loses. 305 306 So the first player (T) wins if and only if there is a pile that has more than $\lfloor \frac{S}{2} \rfloor$ stones or $S$ is odd. This can be easily checked in $O(n)$. 307 308 **C++ solution** 309 310 ``` 311 #include <iostream> 312 #include <vector> 313 #include <algorithm> 314 #include <numeric> 315 316 using namespace std; 317 318 int main() 319 { 320 int t; 321 cin >> t; 322 while (t--) { 323 int n; 324 cin >> n; 325 326 vector<int> a(n); 327 for (int &x : a) cin >> x; 328 329 int maxPile = *max_element(a.begin(), a.end()); 330 int numStones = accumulate(a.begin(), a.end(), 0); 331 332 if (maxPile * 2 > numStones || (numStones & 1)) cout << "T" << endl; 333 else cout << "HL" << endl; 334 } 335 } 336 ``` 337 338 **Python solution** 339 340 ``` 341 t = int(input()) 342 for _ in range(t): 343 n = int(input()) 344 a = [int(x) for x in input().split()] 345 346 maxPile = max(a) 347 numStones = sum(a) 348 349 if maxPile * 2 > numStones or (numStones & 1): 350 print('T') 351 else: 352 print('HL') 353 ``` 354 355 ### [1396C - Monster Invaders](/contest/1396/problem/C "Codeforces Round 666 (Div. 1)") 356 357 In this problem, it is useful to note that when the boss only has $1$ hp left, just use the pistol because it has the least reloading time. So there are 3 strategies we will use when playing at stage $i$ $(1 \le i \le n)$: 358 359 * Take $a_i$ pistol shots to kill first $a_i$ monsters and shoot the boss with the AWP. 360 * Take $a_i + 1$ pistol shots and move back to this stage later to take another pistol shot to finish the boss. 361 * Use the laser gun and move back to this stage later to kill the boss with a pistol shot. 362 363 **Observation:** We will always finish the game at stage $n$ or $n - 1$. Considering we are at stage $i$ $(i \le n - 1)$ and the boss at both stage $i$ stage $i - 1$ has $1$ hp left, we can spend $2 * d$ time to finish both these stages instead of going back later, which costs us exactly the same. 364 365 Therefore, we will calculate $dp(i,0/1)$ as the minimum time to finish first $i - 1$ stages and 0/1 is the remaining hp of the boss at stage $i$. The transitions are easy to figure out by using 3 strategies as above. The only thing we should note is that we can actually finish the game at stage $n - 1$ by instantly kill the boss at stage $n$ with the AWP so we don't have to go back to this level later. 366 367 Answer to the problem is $dp(n, 0)$. Time complexity: $O(n)$. 368 369 **C++ solution** 370 371 ``` 372 /*input 373 4 2 4 4 1 374 4 5 1 2 375 */ 376 #include <bits/stdc++.h> 377 using namespace std; 378 379 int read() { 380 int x = 0, c = getchar(); 381 for(; !(c > 47 && c < 58); c = getchar()); 382 for(; (c > 47 && c < 58); c = getchar()) x = x * 10 + c - 48; 383 return x; 384 } 385 386 void upd(long long &a, long long b) { 387 a = (a < b) ? a : b; 388 } 389 390 const int N = 1e6 + 5; 391 392 long long f[N][2]; 393 int n, r1, r2, r3, d, a[N]; 394 395 int main(){ 396 n = read(), r1 = read(), r2 = read(), r3 = read(), d = read(); 397 for(int i = 1; i <= n; a[i ++] = read()); 398 399 for(int i = 2; i <= n; ++ i) f[i][0] = f[i][1] = 1e18; 400 401 f[1][0] = 1ll * r1 * a[1] + r3; 402 f[1][1] = min(0ll + r2, 1ll * r1 * a[1] + r1); 403 for(int i = 1; i < n; ++ i) { 404 // 0 -> 0 405 // so we clear this one and the next one as well 406 upd(f[i + 1][0], f[i][0] + d + 1ll * r1 * a[i + 1] + r3); 407 408 // 0 -> 1 409 // this one is cleared, but next one isnt 410 upd(f[i + 1][1], f[i][0] + d + min(0ll + r2, 1ll * r1 * a[i + 1] + r1)); 411 412 // 1 -> 0 413 upd(f[i + 1][0], f[i][1] + d + 1ll * r1 * a[i + 1] + r3 + 2 * d + r1); 414 upd(f[i + 1][0], f[i][1] + d + 1ll * r1 * a[i + 1] + r1 + d + r1 + d + r1); 415 upd(f[i + 1][0], f[i][1] + d + r2 + d + r1 + d + r1); 416 417 // 1 -> 1 418 upd(f[i + 1][1], f[i][1] + d + r2 + d + r1 + d); 419 upd(f[i + 1][1], f[i][1] + d + 1ll * r1 * a[i + 1] + r1 + d + r1 + d); 420 421 if(i == n - 1) { 422 upd(f[i + 1][0], f[i][1] + d + 1ll * r1 * a[i + 1] + r3 + d + r1); 423 } 424 } 425 cout << f[n][0] << endl; 426 } 427 ``` 428 429 Tutorial is loading... 430 431 **C++ solution** 432 433 ``` 434 #include <bits/stdc++.h> 435 436 using namespace std; 437 438 using ll = long long; 439 const int MOD = 1000000007; 440 441 int L; 442 ll sum[8040]; 443 int len[8040]; 444 int last[8040]; 445 int lazy[8040]; 446 447 void init(int v, int l, int r, const vector<int> &xs) { 448 len[v] = xs[r] - xs[l - 1]; 449 if (l < r) { 450 int md = (l + r) >> 1; 451 init(v << 1, l, md, xs); 452 init(v << 1 | 1, md + 1, r, xs); 453 } 454 } 455 456 void reset(int v, int l, int r, const vector<int> &go) { 457 lazy[v] = -1; 458 if (l == r) { 459 sum[v] = ll(len[v]) * (L - go[l]); 460 last[v] = go[l]; 461 return; 462 } 463 int md = (l + r) >> 1; 464 reset(v << 1, l, md, go); 465 reset(v << 1 | 1, md + 1, r, go); 466 sum[v] = sum[v << 1] + sum[v << 1 | 1]; 467 last[v] = last[v << 1 | 1]; 468 } 469 470 void push(int v, int l, int r) { 471 if (lazy[v] != -1) { 472 last[v] = lazy[v]; 473 sum[v] = ll(len[v]) * (L - lazy[v]); 474 if (l < r) { 475 lazy[v << 1] = lazy[v]; 476 lazy[v << 1 | 1] = lazy[v]; 477 } 478 lazy[v] = -1; 479 } 480 } 481 482 void modify(int v, int l, int r, int L, int R, int qv) { 483 push(v, l, r); 484 if (L > r || R < l) return; 485 if (L <= l && r <= R) { 486 lazy[v] = qv; 487 push(v, l, r); 488 return; 489 } 490 int md = (l + r) >> 1; 491 modify(v << 1, l, md, L, R, qv); 492 modify(v << 1 | 1, md + 1, r, L, R, qv); 493 sum[v] = sum[v << 1] + sum[v << 1 | 1]; 494 last[v] = last[v << 1 | 1]; 495 } 496 497 int walk(int v, int l, int r, int qv) { 498 push(v, l, r); 499 if (last[v] <= qv) return -1; 500 if (l == r) return l; 501 int md = (l + r) >> 1; 502 int ans = walk(v << 1, l, md, qv); 503 if (ans == -1) ans = walk(v << 1 | 1, md + 1, r, qv); 504 return ans; 505 } 506 507 int main() { 508 ios_base::sync_with_stdio(false); cin.tie(nullptr); 509 int N, K; cin >> N >> K >> L; 510 vector<int> X(N), Y(N), C(N); 511 vector<int> xs = {-1, L}; 512 vector<int> ys = {-1, L}; 513 for (int i = 0; i < N; ++i) { 514 cin >> X[i] >> Y[i] >> C[i]; 515 --C[i]; 516 xs.emplace_back(X[i]); 517 ys.emplace_back(Y[i]); 518 } 519 sort(xs.begin(), xs.end()); 520 xs.resize(unique(xs.begin(), xs.end()) - xs.begin()); 521 sort(ys.begin(), ys.end()); 522 ys.resize(unique(ys.begin(), ys.end()) - ys.begin()); 523 int NX = xs.size(); 524 int NY = ys.size(); 525 { 526 vector<int> order(N); 527 iota(order.begin(), order.end(), 0); 528 sort(order.begin(), order.end(), [&](int i, int j) { 529 return make_pair(Y[i], -X[i]) > make_pair(Y[j], -X[j]); 530 }); 531 vector<int> newX(N), newY(N), newC(N); 532 for (int i = 0; i < N; ++i) { 533 newX[i] = X[order[i]]; 534 newY[i] = Y[order[i]]; 535 newC[i] = C[order[i]]; 536 } 537 X.swap(newX), Y.swap(newY), C.swap(newC); 538 } 539 init(1, 1, NX - 2, xs); 540 int ans = 0; 541 for (int yr = 1; yr + 1 < NY; ++yr) { 542 vector<vector<int>> addAt(NX); 543 for (int i = 0; i < N; ++i) { 544 if (Y[i] <= ys[yr]) { 545 int xi = lower_bound(xs.begin(), xs.end(), X[i]) - xs.begin(); 546 addAt[xi].emplace_back(C[i]); 547 } 548 } 549 int bad = K; 550 vector<int> cnts(K); 551 auto inc = [&](int z) { 552 if (++cnts[z] == 1) --bad; 553 }; 554 auto dec = [&](int z) { 555 if (--cnts[z] == 0) ++bad; 556 }; 557 vector<int> go(NX); 558 int ptr = 0; 559 for (int i = 1; i + 1 < NX; ++i) { 560 while (bad && ptr + 2 < NX) { 561 ptr++; 562 for (int z : addAt[ptr]) inc(z); 563 } 564 if (bad) go[i] = L; 565 else go[i] = xs[ptr]; 566 for (int z : addAt[i]) dec(z); 567 } 568 reset(1, 1, NX - 2, go); 569 vector<int> prv(N); 570 vector<int> nxt(N); 571 vector<map<int, int>> mp(K); 572 for (int i = 0; i < N; ++i) { 573 if (Y[i] <= ys[yr]) { 574 auto it = mp[C[i]].lower_bound(X[i]); 575 if (it == mp[C[i]].end()) { 576 nxt[i] = -1; 577 } else { 578 nxt[i] = it->second; 579 } 580 it = mp[C[i]].upper_bound(X[i]); 581 if (it == mp[C[i]].begin()) { 582 prv[i] = -1; 583 } else { 584 prv[i] = prev(it)->second; 585 } 586 mp[C[i]][X[i]] = i; 587 } 588 } 589 auto remove = [&](int i) { 590 int xprv = (prv[i] == -1 ? -1 : X[prv[i]]); 591 int xcur = X[i]; 592 int xnxt = (nxt[i] == -1 ? L : X[nxt[i]]); 593 int l = lower_bound(xs.begin(), xs.end(), xprv) - xs.begin() + 1; 594 int r = walk(1, 1, NX - 2, xnxt); 595 if (r == -1) r = NX - 1; --r; 596 r = min(r, int(lower_bound(xs.begin(), xs.end(), xcur) - xs.begin())); 597 if (l <= r) modify(1, 1, NX - 2, l, r, xnxt); 598 }; 599 ptr = N - 1; 600 for (int yl = 1; yl <= yr; ++yl) { 601 ll add = sum[1] % MOD * (ys[yr + 1] - ys[yr]) % MOD * (ys[yl] - ys[yl - 1]) % MOD; 602 ans = (ans + add) % MOD; 603 while (ptr >= 0 && Y[ptr] == ys[yl]) remove(ptr--); 604 } 605 assert(sum[1] == 0); 606 } 607 cout << ans << "\n"; 608 return 0; 609 } 610 ``` 611 612 Tutorial is loading... 613 614 **C++ solution** 615 616 ``` 617 #include <bits/stdc++.h> 618 619 using namespace std; 620 621 using ll = long long; 622 623 int main() { 624 ios_base::sync_with_stdio(false); cin.tie(nullptr); 625 int N; ll K; 626 cin >> N >> K; 627 vector<vector<int>> adj(N); 628 for (int i = 0; i < N - 1; ++i) { 629 int v, u; 630 cin >> v >> u; 631 adj[--v].emplace_back(--u); 632 adj[u].emplace_back(v); 633 } 634 vector<int> sz(N); 635 function<void(int, int)> dfs1 = [&](int v, int p) { 636 sz[v] = 1; 637 for (int u : adj[v]) if (u != p) { 638 dfs1(u, v); 639 sz[v] += sz[u]; 640 } 641 }; 642 dfs1(0, -1); 643 int root = 0; 644 for (int i = 1; i < N; ++i) { 645 if (sz[i] >= N / 2 && sz[i] < sz[root]) root = i; 646 } 647 vector<int> dist(N); 648 vector<int> top(N, -1); 649 vector<int> par(N, -1); 650 ll low = 0, high = 0; 651 function<void(int, int, int)> dfs2 = [&](int v, int p, int r) { 652 dist[v] = dist[p] + 1; 653 top[v] = r; 654 par[v] = p; 655 { 656 auto it = find(adj[v].begin(), adj[v].end(), p); 657 assert(it != adj[v].end()); 658 adj[v].erase(it); 659 } 660 sz[v] = 1; 661 for (int u : adj[v]) { 662 dfs2(u, v, r); 663 sz[v] += sz[u]; 664 } 665 low += (sz[v] & 1); 666 high += sz[v]; 667 }; 668 for (int v : adj[root]) { 669 dfs2(v, root, v); 670 } 671 if (low > K || high < K || (high - K) % 2) { 672 cout << "NO\n"; 673 return 0; 674 } 675 set<pair<int, int>> sizes; 676 for (int v : adj[root]) { 677 sizes.emplace(sz[v], v); 678 } 679 vector<set<pair<int, int>>> lcas(N); 680 vector<int> deg(N); 681 for (int v = 0; v < N; ++v) deg[v] = adj[v].size(); 682 for (int v = 0; v < N; ++v) if (v != root) { 683 if (deg[v] == 0) { 684 } else { 685 lcas[top[v]].emplace(dist[v], v); 686 } 687 } 688 vector<bool> matched(N); 689 function<void(int)> kill = [&](int v) { 690 assert(deg[v] == 0); 691 if (--deg[par[v]] == 0) { 692 v = par[v]; 693 lcas[top[v]].erase(pair<int, int>(dist[v], v)); 694 } 695 }; 696 cout << "YES\n"; 697 while (high > K) { 698 assert(sizes.size()); 699 int v = (--sizes.end())->second; 700 sizes.erase(pair<int, int>(sz[v], v)); 701 assert(lcas[v].size()); 702 int mdist = (--lcas[v].end())->first; 703 if (high - 2 * mdist <= K) { 704 int x = lcas[v].lower_bound(pair<int, int>((high - K) / 2, -1))->second; 705 int y = -1; 706 for (int z : adj[x]) if (!matched[z]) { 707 y = z; 708 break; 709 } 710 high = K; 711 cout << x + 1 << " " << y + 1 << "\n"; 712 matched[x] = true; 713 matched[y] = true; 714 break; 715 } else { 716 high -= 2 * mdist; 717 assert(lcas[v].size()); 718 int u = (--lcas[v].end())->second; 719 vector<int> nxts; 720 while (nxts.size() < 2 && adj[u].size()) { 721 int w = adj[u].back(); 722 adj[u].pop_back(); 723 if (!matched[w]) { 724 nxts.emplace_back(w); 725 } 726 } 727 if (nxts.size() < 2) nxts.emplace_back(u); 728 assert(nxts.size() == 2); 729 cout << nxts[0] + 1 << " " << nxts[1] + 1 << "\n"; 730 matched[nxts[0]] = true; 731 matched[nxts[1]] = true; 732 kill(nxts[0]); 733 kill(nxts[1]); 734 sz[v] -= 2; 735 if (sz[v]) sizes.emplace(sz[v], v); 736 } 737 } 738 vector<int> seq; 739 function<void(int)> dfs3 = [&](int v) { 740 if (!matched[v]) seq.emplace_back(v); 741 for (int u : adj[v]) dfs3(u); 742 }; 743 dfs3(root); 744 int h = seq.size() / 2; 745 for (int i = 0; i < h; ++i) { 746 cout << seq[i] + 1 << " " << seq[i + h] + 1 << "\n"; 747 } 748 } 749 ```