1691.md (20730B)
1 Source: https://codeforces.com/blog/entry/103212 2 3 # [1691A - Beat The Odds](/contest/1691/problem/A "CodeCraft-22 and Codeforces Round 795 (Div. 2)") 4 5 **[Video Editorial](https://youtu.be/CwsYQXjIwDg)** 6 **Idea:** [amul_agrawal](/profile/amul_agrawal "Master amul_agrawal") 7 **Problem Setting:** [menavlikar.rutvij](/profile/menavlikar.rutvij "Expert menavlikar.rutvij") [JadeReaper](/profile/JadeReaper "Expert JadeReaper") [rahulgoel](/profile/rahulgoel "Expert rahulgoel") [amul_agrawal](/profile/amul_agrawal "Master amul_agrawal") 8 **Editorial**: [menavlikar.rutvij](/profile/menavlikar.rutvij "Expert menavlikar.rutvij") [rahulgoel](/profile/rahulgoel "Expert rahulgoel") 9 **Video Editorial**: [rahulgoel](/profile/rahulgoel "Expert rahulgoel") 10 11 **Hint 1** 12 13 Sum of two odd numbers is even and sum of two even numbers is also even. 14 15 **Hint 2** 16 17 If all consecutive pairs have even sum, can we generalize something about the sequence using the above hint? 18 19 **Solution** 20 21 Tutorial is loading... 22 23 **C++ Code** 24 25 ``` 26 #include <bits/stdc++.h> 27 28 using namespace std; 29 30 int main() 31 { 32 int t; 33 cin >> t; 34 while (t--) 35 { 36 int n; 37 cin >> n; 38 vector<int> a(n); 39 for (int i = 0; i < n; ++i) 40 cin >> a[i]; 41 int num_odd = 0; 42 for (auto x : a) 43 if (x & 1) 44 num_odd++; 45 cout << min(num_odd, n - num_odd) << endl; 46 } 47 return 0; 48 } 49 ``` 50 51 # [1691B - Shoe Shuffling](/contest/1691/problem/B "CodeCraft-22 and Codeforces Round 795 (Div. 2)") 52 53 **[Video Editorial](https://youtu.be/ZA1qvxn7lP0)** 54 **Idea:** [amul_agrawal](/profile/amul_agrawal "Master amul_agrawal") 55 **Problem Setting:** [rahulgoel](/profile/rahulgoel "Expert rahulgoel") [menavlikar.rutvij](/profile/menavlikar.rutvij "Expert menavlikar.rutvij") [JadeReaper](/profile/JadeReaper "Expert JadeReaper") 56 **Editorial**: [menavlikar.rutvij](/profile/menavlikar.rutvij "Expert menavlikar.rutvij") [rahulgoel](/profile/rahulgoel "Expert rahulgoel") 57 **Video Editorial**: [JadeReaper](/profile/JadeReaper "Expert JadeReaper") 58 59 **Hint 1** 60 61 What happens to other people when a person receives a shoe greater his size? 62 63 **Hint 2** 64 65 What happens when a person has a unique shoe size? 66 67 **Solution** 68 69 Tutorial is loading... 70 71 **C++ Code** 72 73 ``` 74 #include <bits/stdc++.h> 75 76 using namespace std; 77 78 #define ll long long 79 typedef vector<ll> vll; 80 #define io \ 81 ios_base::sync_with_stdio(false); \ 82 cin.tie(NULL); \ 83 cout.tie(NULL) 84 85 int main() 86 { 87 io; 88 ll tc; 89 cin >> tc; 90 while (tc--) 91 { 92 ll n; 93 cin >> n; 94 vll s(n), p(n); 95 for (ll i = 0; i < n; ++i) 96 cin >> s[i]; 97 98 ll l = 0, r = 0; 99 bool ans = true; 100 for (ll i = 0; i < n; ++i) 101 p[i] = i + 1; 102 103 while (r < n) 104 { 105 while (r < n - 1 and s[r] == s[r + 1]) // get range [l,r] with equal values 106 ++r; 107 if (l == r) 108 ans = false; 109 else 110 rotate(p.begin() + l, p.begin() + r, p.begin() + r + 1); // rotate right in range [l,r] 111 l = r + 1; 112 ++r; 113 } 114 if (ans) 115 { 116 for (auto &x : p) 117 cout << x << " "; 118 cout << endl; 119 } 120 else 121 cout << -1 << endl; 122 } 123 return 0; 124 } 125 ``` 126 127 # [1691C - Sum of Substrings](/contest/1691/problem/C "CodeCraft-22 and Codeforces Round 795 (Div. 2)") 128 129 **[Video Editorial](https://youtu.be/AP98uwI-R90)** 130 **Idea:** [amul_agrawal](/profile/amul_agrawal "Master amul_agrawal") 131 **Problem Setting:** [rahulgoel](/profile/rahulgoel "Expert rahulgoel") [amul_agrawal](/profile/amul_agrawal "Master amul_agrawal") 132 **Editorial**: [amul_agrawal](/profile/amul_agrawal "Master amul_agrawal") [rahulgoel](/profile/rahulgoel "Expert rahulgoel") 133 **Video Editorial**: [amul_agrawal](/profile/amul_agrawal "Master amul_agrawal") 134 135 **Hint 1** 136 137 What is the contribution of each `1`? 138 139 **Hint 2** 140 141 At what position would `1` contribute less? 142 143 **Solution** 144 145 Tutorial is loading... 146 147 **C++ Code** 148 149 ``` 150 #include <bits/stdc++.h> 151 using namespace std; 152 153 int main() { 154 ios_base::sync_with_stdio(false); 155 cin.tie(NULL); 156 int t; 157 cin >> t; 158 while (t--) { 159 int n, k; 160 cin >> n >> k; 161 string s; 162 cin >> s; 163 int ones = 0, p1_first = n, p1_last = -1; 164 for (int p = 0; p < n; p++) { 165 if (s[p] != '1') 166 continue; 167 ones += 1; 168 if (p1_first == n) 169 p1_first = p; 170 p1_last = p; 171 } 172 int add = 0; 173 // moving the last one to last position 174 if (ones > 0 and (n - 1 - p1_last) <= k) { 175 k -= (n - 1 - p1_last); 176 add += 1; 177 ones -= 1; 178 } 179 // moving the first one to first position 180 if (ones > 0 and p1_first <= k) { 181 k -= (p1_first); 182 add += 10; 183 ones -= 1; 184 } 185 cout << 11 * ones + add << "\n"; 186 } 187 return 0; 188 } 189 ``` 190 191 # [1691D - Max GEQ Sum](/contest/1691/problem/D "CodeCraft-22 and Codeforces Round 795 (Div. 2)") 192 193 **[Video Editorial](https://youtu.be/ZH9AonbvPAA)** 194 **Idea:** [amul_agrawal](/profile/amul_agrawal "Master amul_agrawal") 195 **Problem Setting:** [fangahawk](/profile/fangahawk "Candidate Master fangahawk") [amul_agrawal](/profile/amul_agrawal "Master amul_agrawal") [rahulgoel](/profile/rahulgoel "Expert rahulgoel") [keyurchd_11](/profile/keyurchd_11 "Candidate Master keyurchd_11") 196 **Editorial**: [fangahawk](/profile/fangahawk "Candidate Master fangahawk") [rahulgoel](/profile/rahulgoel "Expert rahulgoel") 197 **Video Editorial**: [fangahawk](/profile/fangahawk "Candidate Master fangahawk") 198 199 **Hint 1** 200 201 If we have a list of subarrays where the element at index $i$ is the max, which subarrays should we check to be sufficient? 202 203 **Hint 2** 204 205 Checking subarrays which end or start at index $i$ is sufficient, so we can optimize our solution with this observation as the basis. 206 207 **Solution** 208 209 Tutorial is loading... 210 211 **C++ Code** 212 213 ``` 214 #include <bits/stdc++.h> 215 typedef long long ll; 216 using namespace std; 217 218 const ll ninf = -1e15; 219 220 vector<int> nextGreater(vector<ll>& arr, int n) { 221 stack<int> s; 222 vector<int> result(n, n); 223 for (int i = 0; i < n; i++) { 224 while (!s.empty() && arr[s.top()] < arr[i]) { 225 result[s.top()] = i; 226 s.pop(); 227 } 228 s.push(i); 229 } 230 return result; 231 } 232 233 vector<int> prevGreater(vector<ll>& arr, int n) { 234 stack<int> s; 235 vector<int> result(n, -1); 236 for (int i = n - 1; i >= 0; i--) { 237 while (!s.empty() && arr[s.top()] < arr[i]) { 238 result[s.top()] = i; 239 s.pop(); 240 } 241 s.push(i); 242 } 243 return result; 244 } 245 246 ll query(vector<ll> &tree, int node, int ns, int ne, int qs, int qe) { 247 if (qe < ns || qs > ne) return ninf; 248 if (qs <= ns && ne <= qe) return tree[node]; 249 250 int mid = ns + (ne - ns) / 2; 251 ll leftQuery = query(tree, 2 * node, ns, mid, qs, qe); 252 ll rightQuery = query(tree, 2 * node + 1, mid + 1, ne, qs, qe); 253 return max(leftQuery, rightQuery); 254 } 255 256 int main() { 257 int t; 258 cin >> t; 259 while (t--) { 260 int n, _n; 261 cin >> n; 262 vector<ll> arr(n, 0); 263 for (auto& a : arr) 264 cin >> a; 265 266 // Round off n to next power of 2 267 _n = n; 268 while (__builtin_popcount(_n) != 1) _n++; 269 270 271 // Prefix sums 272 vector<ll> prefixSum(n, 0), suffixSum(n, 0); 273 prefixSum[0] = arr[0]; 274 for (int i = 1; i < n; i++) { 275 prefixSum[i] = prefixSum[i - 1] + arr[i]; 276 } 277 suffixSum[n - 1] = arr[n - 1]; 278 for (int i = n - 2; i >= 0; i--) { 279 suffixSum[i] = suffixSum[i + 1] + arr[i]; 280 } 281 282 // Two max-segtress, one on the prefix sums, one on the suffix sums 283 vector<ll> prefixTree(2 * _n, ninf), suffixTree(2 * _n, ninf); 284 285 for (int i = 0; i < n; i++) { 286 prefixTree[_n + i] = prefixSum[i]; 287 suffixTree[_n + i] = suffixSum[i]; 288 } 289 290 for (int i = _n - 1; i >= 1; i--) { 291 prefixTree[i] = max(prefixTree[2 * i], prefixTree[2 * i + 1]); 292 suffixTree[i] = max(suffixTree[2 * i], suffixTree[2 * i + 1]); 293 } 294 vector<int> ng = nextGreater(arr, n); 295 vector<int> pg = prevGreater(arr, n); 296 bool flag = true; 297 298 for (int i = 0; i < n; i++) { 299 ll rightMax = query(prefixTree, 1, 0, _n - 1, i + 1, ng[i] - 1) - prefixSum[i]; 300 ll leftMax = query(suffixTree, 1, 0, _n - 1, pg[i] + 1, i - 1) - suffixSum[i]; 301 if (max(leftMax, rightMax) > 0) { 302 flag = false; 303 break; 304 } 305 } 306 if (flag) 307 cout << "YES\n"; 308 else 309 cout << "NO\n"; 310 } 311 } 312 ``` 313 314 # [1691E - Number of Groups](/contest/1691/problem/E "CodeCraft-22 and Codeforces Round 795 (Div. 2)") 315 316 **[Video Editorial](https://youtu.be/zHpH25DUqz4)** 317 **Idea:** [amul_agrawal](/profile/amul_agrawal "Master amul_agrawal") 318 **Problem Setting:** [akcube](/profile/akcube "Expert akcube") [keyurchd_11](/profile/keyurchd_11 "Candidate Master keyurchd_11") [rahulgoel](/profile/rahulgoel "Expert rahulgoel") [amul_agrawal](/profile/amul_agrawal "Master amul_agrawal") 319 **Editorial**: [akcube](/profile/akcube "Expert akcube") [rahulgoel](/profile/rahulgoel "Expert rahulgoel") [keyurchd_11](/profile/keyurchd_11 "Candidate Master keyurchd_11") 320 **Video Editorial**: [akcube](/profile/akcube "Expert akcube") 321 322 **Hint 1** 323 324 We can iterate over the starting and ending points of all segments. 325 326 **Hint 2** 327 328 Is it necessary to connect all segments which can be connected? 329 Can we make observations which would reduce the number of connections we actually make? 330 331 **Hint 3** 332 333 For each group formed, it is enough to store the blue segment with maximum ending point, and red segment with maximum ending point. 334 335 **Solution** 336 337 Tutorial is loading... 338 339 **C++ Code** 340 341 ``` 342 #include <bits/stdc++.h> 343 using namespace std; 344 345 #include <ext/pb_ds/assoc_container.hpp> 346 #include <ext/pb_ds/tree_policy.hpp> 347 using namespace __gnu_pbds; 348 template <class T> 349 using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; 350 351 #define MOD 1000000007 352 typedef long long ll; 353 354 typedef pair<int, int> pii; 355 typedef vector<int> vi; 356 #define pb push_back 357 #define all(s) s.begin(), s.end() 358 #define sz(x) (int)(x).size() 359 #define fastio cin.tie(0) -> sync_with_stdio(0) 360 361 struct DSU{ 362 vi dsu, szx; 363 364 DSU() = default; 365 DSU(int n) : dsu(n), szx(n, 1) { 366 for(int i=0; i<n; i++) dsu[i] = i; 367 } 368 369 int parent(int i){ 370 if(dsu[i]==i) return i; 371 else return dsu[i] = parent(dsu[i]); 372 } 373 374 int size(int i) { return szx[parent(i)]; } 375 int operator[](int i){ return parent(i); } 376 int num_comps(){ 377 int ct = 0; 378 for(int i=0; i<sz(dsu); i++) if(dsu[i] == i) ct++; 379 return ct; 380 } 381 382 void unify(int a, int b){ 383 a = parent(a); 384 b = parent(b); 385 if(szx[a] < szx[b]) swap(a, b); 386 if(a!=b) dsu[b] = a, szx[a] += szx[b]; 387 } 388 }; 389 390 struct Point{ 391 int t, p, pc, id; 392 bool close; 393 bool operator<(Point &other){ 394 if(p == other.p) return close < other.close; 395 return p < other.p; 396 } 397 }; 398 399 void solve(){ 400 401 int n; cin>>n; 402 vector<Point> points; 403 for(int i=0; i<n; i++){ 404 int t, l, r; cin>>t>>l>>r; 405 points.pb({t, l, r, i, false}); 406 points.pb({t, r, l, i, true}); 407 } 408 sort(all(points)); 409 410 DSU dsu(n); 411 vector<set<pii>> open(2); // {r, id} 412 for(auto &p:points){ 413 if(p.close) open[p.t].erase({p.p, p.id}); 414 else{ 415 open[p.t].insert({p.pc, p.id}); 416 while(sz(open[p.t ^ 1]) > 1){ 417 auto [r, id] = *open[p.t ^ 1].begin(); 418 dsu.unify(p.id, id); 419 open[p.t ^ 1].erase({r, id}); 420 } 421 if(sz(open[p.t ^ 1]) == 1) dsu.unify(p.id, open[p.t ^ 1].begin()->second); 422 } 423 } 424 425 cout<<dsu.num_comps()<<endl; 426 } 427 428 int main(){ 429 fastio; 430 int t; 431 cin >> t; 432 while (t--) solve(); 433 } 434 ``` 435 436 [darkkcyan](/profile/darkkcyan "Grandmaster darkkcyan")'s solution without using sets in python. 437 438 **Python code** 439 440 ``` 441 from sys import stdin 442 443 def solve_case(): 444 n = int(stdin.readline()) 445 segs = [tuple(map(int, stdin.readline().split())) + (i, ) for i in range(n)] 446 segs.sort(key=lambda x: x[1]) 447 448 par = [-1] * n 449 cnt_comp = n 450 def find_set(u): 451 p = u 452 while par[p] >= 0: 453 p = par[p] 454 while u != p: 455 t = par[u] 456 par[u] = p 457 u = t 458 return p 459 460 def join(u, v): 461 nonlocal cnt_comp 462 nonlocal par 463 u = find_set(u) 464 v = find_set(v) 465 if u == v: 466 return 467 if -par[u] < -par[v]: 468 u, v = v, u 469 par[u] += par[v] 470 par[v] = u 471 cnt_comp -= 1 472 473 hp = [[], []] 474 475 for col, l, r, id in segs: 476 for elm in hp[1 - col]: 477 if elm[0] < l: 478 continue 479 join(elm[1], id) 480 if len(hp[1 - col]): 481 hp[1 - col] = [max(hp[1 - col])] 482 hp[col].append((r, id)) 483 return cnt_comp 484 485 for testcase in range(int(stdin.readline())): 486 print(solve_case()) 487 ``` 488 489 [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")'s $nlog^3n$ solution for E using Boruvka and Mergesort tree :D 490 491 **Code** 492 493 ``` 494 #include <bits/stdc++.h> 495 using namespace std; 496 497 #define nl "\n" 498 #define nf endl 499 #define ll int 500 #define pb push_back 501 #define _ << ' ' << 502 #define tm gfewnignefgo 503 504 #define INF (int)1e9 505 #define mod 998244353 506 #define maxn 200010 507 508 ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b; 509 ll c[maxn], l[maxn], r[maxn], pr[maxn], sz[maxn]; 510 ll tm, df[maxn]; 511 vector<ll> adj[maxn]; 512 vector<array<ll, 2>> nd; 513 vector<array<ll, 3>> cm; 514 priority_queue<array<ll, 2>> fn[2][maxn]; 515 516 ll find(ll x) { 517 if (x == pr[x]) return x; 518 return pr[x] = find(pr[x]); 519 } 520 521 bool same(ll a, ll b) { 522 return (find(a) == find(b)); 523 } 524 525 void onion(ll a, ll b) { 526 a = find(a); b = find(b); 527 if (a == b) return; 528 if (sz[a] < sz[b]) swap(a, b); 529 pr[b] = a; sz[a] += sz[b]; 530 } 531 532 void upd(ll c, ll p, ll x, ll id) { 533 while (p < maxn) { 534 fn[c][p].push({x, id}); p += (p & (-p)); 535 } 536 } 537 538 void nts(ll c, ll p, ll r, ll st) { 539 ll wn = -1; 540 for (; p > 0; p -= (p & (-p))) { 541 while (!fn[c][p].empty()) { 542 auto [rr, id] = fn[c][p].top(); 543 if (!df[id]) { 544 fn[c][p].pop(); continue; 545 } 546 if (rr < r) break; 547 wn = id; break; 548 } 549 if (wn != -1) { 550 nd.pb({st, wn}); break; 551 } 552 } 553 } 554 555 int main() { 556 ios::sync_with_stdio(0); 557 cin.tie(0); 558 559 #if !ONLINE_JUDGE && !EVAL 560 ifstream cin("input.txt"); 561 ofstream cout("output.txt"); 562 #endif 563 564 // today I'm overkilling everything 565 // tl;dr mst with boruvka and merge sort tree, O(n*log^3(n)), let's hope it gets ac 566 567 cin >> t; 568 while (t--) { 569 cin >> n; 570 for (i = 1; i <= 2 * n; i++) { 571 while (!fn[0][i].empty()) fn[0][i].pop(); 572 while (!fn[1][i].empty()) fn[1][i].pop(); 573 } 574 for (i = 1; i <= n; i++) { 575 cin >> c[i] >> l[i] >> r[i]; 576 pr[i] = i; sz[i] = 1; 577 } 578 579 cm.clear(); cm.pb({-INF, 0, 0}); 580 for (i = 1; i <= n; i++) { 581 cm.pb({l[i], i, 0}); cm.pb({r[i], i, 1}); 582 } 583 584 sort(cm.begin(), cm.end()); 585 for (i = 1; i <= 2 * n; i++) { 586 if (i == 1 || cm[i][0] != cm[i - 1][0]) k = i; 587 if (cm[i][2] == 0) l[cm[i][1]] = k; 588 else r[cm[i][1]] = k; 589 } 590 591 for (i = 1; i <= n; i++) { 592 upd(c[i], l[i], r[i], i); df[i] = true; 593 } 594 595 while (true) { 596 nd.clear(); 597 for (i = 1; i <= n; i++) adj[i].clear(); 598 for (i = 1; i <= n; i++) adj[find(i)].pb(i); 599 for (i = 1; i <= n; i++) { 600 for (auto u : adj[i]) df[u] = false; 601 for (auto u : adj[i]) nts(c[u] ^ 1, r[u], l[u], u); 602 for (auto u : adj[i]) { 603 df[u] = true; upd(c[u], l[u], r[u], u); 604 } 605 } 606 607 if (nd.empty()) break; 608 for (auto [a, b] : nd) onion(a, b); 609 } 610 611 res = 0; 612 for (i = 1; i <= n; i++) { 613 if (find(i) == i) res++; 614 } 615 cout << res << nl; 616 } 617 return 0; 618 } 619 ``` 620 621 # [1691F - K-Set Tree](/contest/1691/problem/F "CodeCraft-22 and Codeforces Round 795 (Div. 2)") 622 623 **[Video Editorial](https://youtu.be/o8NjLKYR7iM)** 624 **Idea:** [ltc.groverkss](/profile/ltc.groverkss "Master ltc.groverkss") 625 **Problem Setting:** [ltc.groverkss](/profile/ltc.groverkss "Master ltc.groverkss") [amul_agrawal](/profile/amul_agrawal "Master amul_agrawal") [rahulgoel](/profile/rahulgoel "Expert rahulgoel") 626 **Editorial**: [rahulgoel](/profile/rahulgoel "Expert rahulgoel") 627 **Video Editorial**: [rahulgoel](/profile/rahulgoel "Expert rahulgoel") 628 629 **Hint 1** 630 631 Can we root the tree and find the partial answer for a paticular root? 632 633 **Hint 2** 634 635 The counting problem for a fixed root can be solved using combinatorics. 636 637 **Hint 3** 638 639 Can we find the answer for other roots using the calculations involved in finding answer for a fixed root in Hint 1? 640 641 **Solution** 642 643 Tutorial is loading... 644 645 **C++ Code** 646 647 ``` 648 #include <iostream> 649 #include <vector> 650 651 using namespace std; 652 using ll = long long; 653 654 const ll MOD = 1e9 + 7; 655 656 struct Comb { 657 vector<ll> fac; 658 vector<ll> invfac; 659 ll n; 660 661 Comb(ll n) 662 { 663 this->n = n; 664 fac.resize(n + 1, 0); 665 invfac.resize(n + 1, 0); 666 667 fac[0] = 1; 668 for (ll i = 1; i <= n; i++) 669 fac[i] = (fac[i - 1] * i) % MOD; 670 invfac[n] = power(fac[n], MOD - 2); 671 for (ll i = n - 1; i >= 0; i--) 672 invfac[i] = (invfac[i + 1] * (i + 1)) % MOD; 673 } 674 675 static ll power(ll x, ll y) 676 { 677 ll ret = 1; 678 while (y) { 679 if (y & 1) 680 ret = (ret * x) % MOD; 681 y >>= 1; 682 x = (x * x) % MOD; 683 } 684 return ret; 685 } 686 687 ll nCr(ll n, ll r) 688 { 689 if (n < 0 or r < 0 or n < r) 690 return 0; 691 ll ans = (fac[n] * ((invfac[r] * invfac[n - r]) % MOD)) % MOD; 692 return ans; 693 } 694 }; 695 696 vector<vector<int> > adj; 697 vector<int> sz; 698 vector<ll> cnt; 699 vector<ll> cntsz; 700 701 Comb C(2e5 + 5); 702 703 ll cur_ans = 0; 704 ll ans = 0; 705 706 void dfs1(int v, int p, int k) 707 { 708 sz[v] = 1; 709 ll sub = 0; 710 711 for (int u : adj[v]) { 712 if (u != p) { 713 dfs1(u, v, k); 714 sz[v] += sz[u]; 715 sub = (sub + C.nCr(sz[u], k)) % MOD; 716 } 717 } 718 719 cnt[v] = (C.nCr(sz[v], k) - sub + MOD) % MOD; 720 cntsz[v] = (cnt[v] * sz[v]) % MOD; 721 cur_ans = (cur_ans + cntsz[v]) % MOD; 722 } 723 724 void dfs2(int v, int p, int k) 725 { 726 ans = (ans + cur_ans) % MOD; 727 for (int u : adj[v]) { 728 if (u != p) { 729 // store 730 int store_v_sz = sz[v]; 731 ll store_v_cnt = cnt[v]; 732 ll store_v_cntsz = cntsz[v]; 733 int store_u_sz = sz[u]; 734 ll store_u_cnt = cnt[u]; 735 ll store_u_cntsz = cntsz[u]; 736 ll store_cur_ans = cur_ans; 737 738 // recalculate size[v], size[u] 739 sz[v] -= sz[u]; 740 sz[u] = sz.size(); 741 742 // recalculate cnt[v] 743 cnt[v] = (cnt[v] - C.nCr(store_v_sz, k) + MOD) % MOD; 744 cnt[v] = (cnt[v] + C.nCr(sz[v], k)) % MOD; 745 cnt[v] = (cnt[v] + C.nCr(store_u_sz, k)) % MOD; 746 747 // recalculate cnt[u] 748 cnt[u] = (cnt[u] - C.nCr(store_u_sz, k) + MOD) % MOD; 749 cnt[u] = (cnt[u] + C.nCr(sz[u], k)) % MOD; 750 cnt[u] = (cnt[u] - C.nCr(sz[v], k) + MOD) % MOD; 751 752 // recalculate cntsz 753 cntsz[v] = (cnt[v] * sz[v]) % MOD; 754 cntsz[u] = (cnt[u] * sz[u]) % MOD; 755 756 // recalculate cur_ans 757 cur_ans = (cur_ans - store_v_cntsz - store_u_cntsz + MOD + MOD) % MOD; 758 cur_ans = (cur_ans + cntsz[v] + cntsz[u]) % MOD; 759 760 dfs2(u, v, k); 761 762 // restore 763 sz[v] = store_v_sz; 764 cnt[v] = store_v_cnt; 765 cntsz[v] = store_v_cntsz; 766 sz[u] = store_u_sz; 767 cnt[u] = store_u_cnt; 768 cntsz[u] = store_u_cntsz; 769 cur_ans = store_cur_ans; 770 } 771 } 772 } 773 774 int main() 775 { 776 ios_base::sync_with_stdio(0); 777 cin.tie(0); 778 cout.tie(0); 779 780 int n, k; 781 cin >> n >> k; 782 783 adj.resize(n); 784 sz.resize(n); 785 cnt.resize(n); 786 cntsz.resize(n); 787 788 for (int i = 0; i < n - 1; ++i) { 789 int u, v; 790 cin >> u >> v; 791 --u, --v; 792 adj[u].push_back(v); 793 adj[v].push_back(u); 794 } 795 796 dfs1(0, 0, k); 797 dfs2(0, 0, k); 798 799 cout << ans << endl; 800 return 0; 801 } 802 ```