codeforces-scrape

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

1397.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 ```