codeforces-scrape

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

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