codeforces-scrape

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

1778.md (17374B)


      1 Source: https://codeforces.com/blog/entry/112149
      2 
      3 [1778A - Flip Flop Sum](/contest/1778/problem/A "Codeforces Round 848 (Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Code**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 using namespace std;
     14  
     15 const int sz = 1e5 + 10;
     16 int ara[sz];
     17  
     18 int main()
     19 {
     20     int t;
     21     scanf("%d", &t);
     22  
     23     while(t--) {
     24         int n;
     25         scanf("%d", &n);
     26  
     27         int sum = 0;
     28  
     29         for(int i = 1; i <= n; i++) {
     30             scanf("%d", &ara[i]);
     31             sum += ara[i];
     32         }
     33  
     34         int ans = -1e9;
     35  
     36         for(int i = 1; i < n; i++) {
     37             if(ara[i] == ara[i+1]) {
     38                 if(ara[i] == 1) ans = max(ans, sum-4);
     39                 else ans = max(ans, sum+4);
     40             }
     41             else
     42                 ans = max(ans, sum);
     43         }
     44  
     45         printf("%d\n", ans);
     46     }
     47  
     48     return 0;
     49 }
     50 ```
     51 
     52 [1778B - The Forbidden Permutation](/contest/1778/problem/B "Codeforces Round 848 (Div. 2)")
     53 
     54 **Tutorial**
     55 
     56 Tutorial is loading...
     57 
     58 **Code**
     59 
     60 ```
     61 #include <bits/stdc++.h>
     62 using namespace std;
     63  
     64 const int sz = 1e5+10;
     65 int p[sz], a[sz], pos[sz];
     66  
     67 int main()
     68 {
     69     int t;
     70     scanf("%d", &t);
     71  
     72     while(t--) {
     73         int n, m, d;
     74         scanf("%d %d %d", &n, &m, &d);
     75  
     76         for(int i = 1; i <= n; i++) {
     77             scanf("%d", &p[i]);
     78             pos[ p[i] ] = i;
     79         }
     80  
     81         for(int i = 1; i <= m; i++) {
     82             scanf("%d", &a[i]);
     83         }
     84  
     85         int ans = 1e9;
     86  
     87         for(int i = 1; i < m; i++) {
     88             if(pos[a[i+1]] <= pos[a[i]] || pos[a[i+1]]-pos[a[i]] > d) {
     89                 ans = 0;
     90                 break;
     91             }
     92  
     93             ans = min(ans, pos[a[i+1]] - pos[a[i]]);
     94  
     95             int dist = pos[a[i+1]]-pos[a[i]];
     96  
     97             int swapNeed = d-dist+1;
     98             int swapPossible = (pos[a[i]]-1) + (n - pos[a[i+1]]);
     99             if(swapPossible >= swapNeed) ans = min(ans, swapNeed);
    100         }
    101  
    102         printf("%d\n", ans);
    103     }
    104  
    105     return 0;
    106 }
    107 ```
    108 
    109 [1778C - Flexible String](/contest/1778/problem/C "Codeforces Round 848 (Div. 2)")
    110 
    111 **Tutorial**
    112 
    113 Tutorial is loading...
    114 
    115 **Code**
    116 
    117 ```
    118 #include <bits/stdc++.h>
    119 using namespace std;
    120  
    121 #define ll long long
    122 #define pb push_back
    123 #define EL '\n'
    124 #define fastio std::ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    125  
    126 string a, b;
    127 string char_list;
    128 bool mark[26];
    129 ll ans, k;
    130  
    131 ll count_matching_pair()
    132 {
    133     ll tot_pair = 0, match_count = 0;
    134  
    135     for(ll i = 0; i < a.size(); i++) {
    136         if(a[i] == b[i] || mark[ a[i]-'a' ])
    137             match_count++;
    138         else {
    139             tot_pair += match_count*(match_count+1)/2;
    140             match_count = 0;
    141         }
    142     }
    143     tot_pair += match_count*(match_count+1)/2;
    144  
    145     return tot_pair;
    146 }
    147  
    148 void solve(ll pos, ll cnt)
    149 {
    150     if(cnt > k) return;
    151  
    152     if(pos == char_list.size()) {
    153         if(cnt == k) ans = max(ans, count_matching_pair());
    154         return;
    155     }
    156  
    157     solve(pos+1, cnt);
    158  
    159     mark[ char_list[pos]-'a' ] = 1;
    160     solve(pos+1, cnt+1);
    161     mark[ char_list[pos]-'a' ] = 0;
    162 }
    163  
    164 int main()
    165 {
    166     fastio;
    167     ll t;
    168     cin >> t;
    169  
    170     while(t--) {
    171         ll n; cin >> n >> k;
    172         cin >> a >> b;
    173  
    174         unordered_set <char> unq;
    175         for(auto &ch : a) unq.insert(ch);
    176  
    177         char_list.clear();
    178         for(auto &x : unq) char_list.pb(x);
    179  
    180         k = min(k, (ll)unq.size());
    181         memset(mark, 0, sizeof mark);
    182         ans = 0;
    183         solve(0, 0);
    184  
    185         cout << ans << EL;
    186     }
    187  
    188     return 0;
    189 }
    190 ```
    191 
    192 [1778D - Flexible String Revisit](/contest/1778/problem/D "Codeforces Round 848 (Div. 2)")
    193 
    194 **Tutorial**
    195 
    196 ### [1778D - Flexible String Revisit](/contest/1778/problem/D "Codeforces Round 848 (Div. 2)")
    197 
    198 Let $k$ be the number of indices where the characters between two strings are different and $f(x)$ be the expected number of moves to make two strings equal given that the strings have $x$ differences. We have to find the value of $f(k)$.
    199 
    200 For all $x$ where $1 \leq x \leq n-1$,
    201 
    202 $ \begin{align} f(x) = \frac{x}{n} \cdot [1 + f(x-1)] + \frac{n-x}{n} \cdot [1 + f(x+1)]\\ or,~~~ f(x) = 1 + \frac{x}{n}\cdot f(x-1) + \frac{n-x}{n} \cdot f(x+1) \end{align} $
    203 
    204 Now, $f(0) = 0$ and $f(1) = 1 + \frac{n-1}{n}f(2)$.
    205 
    206 We can represent any $f(i)$ in the form $f(i) = a_i + b_i \cdot f(i+1)$.
    207 
    208 Let, $a_{1} = 1$ and $b_{1} = \frac{n-1}{n}$. So, we can write $f(1) = a_{1} + b_{1}\cdot f(2)$.
    209 
    210 When $1 \lt i \lt n$, $f(i) = 1 + \frac{i}{n} \cdot f(i-1) + \frac{n-i}{n} \cdot f(i+1)$. We can substitute the value of $f(i-1)$ with $a_{i-1} + b_{i-1}\cdot f(i)$ and calculate the value of $f(i)$. Thus we can get the value of $a_i$ and $b_i$ using the value of $a_{i-1}$ and $b_{i-1}$ by considering $a_1$ and $b_1$ as the base case.
    211 
    212 We get, $a_{i} = \frac{n+i\cdot a_{i-1}}{n-i\cdot b_{i-1}}$ and $b_{i} = \frac{n-i}{n-i \cdot b_{i-1}}$ for $2 \leq i \leq n$.
    213 
    214 **Calculation**
    215 
    216 Substituting $f(i-1) = a_{i-1} + b_{i-1}\cdot f(i)$,
    217 
    218 $ \begin{align} f(i) & = 1 + \frac{i}{n} \cdot [a_{i-1} + b_{i-1}\cdot f(i)] + \frac{n-i}{n} \cdot f(i+1)\\ & = 1 + \frac{i}{n}\cdot a_{i-1} + \frac{i}{n} \cdot b_{i-1} \cdot f(i) + \frac{n-i}{n} \cdot f(i+1)\\ & = \frac{1+\frac{i}{n}\cdot a_{i-1}}{1-\frac{i}{n}\cdot b_{i-1}} + \frac{n-i}{n-i \cdot b_{i-1}}f(i+1)\\ & = \frac{n+i\cdot a_{i-1}}{n-i\cdot b_{i-1}} + \frac{n-i}{n-i \cdot b_{i-1}}f(i+1)\\ & = a_{i} + b_{i} \cdot f(i+1) \end{align} $
    219 
    220 So, $a_{i} = \frac{n+i\cdot a_{i-1}}{n-i\cdot b_{i-1}}$ and $b_{i} = \frac{n-i}{n-i \cdot b_{i-1}}$ for $2 \leq i \leq n$.
    221 
    222 Similarly, $f(n) = 1+f(n-1)$.
    223 
    224 We can represent any $f(i)$ in the form $f(i) = c_i + d_i \cdot f(i-1)$.
    225 
    226 Let, $c_{n} = 1$ and $d_{n} = 1$. So, we can write $f(n) = c_{n} + d_{n}\cdot f(n-1)$.
    227 
    228 When $1 \lt i \lt n$, $f(i) = 1 + \frac{i}{n} \cdot f(i-1) + \frac{n-i}{n} \cdot f(i+1)$. We can substitute the value of $f(i+1)$ with $c_{i+1} + d_{i+1}\cdot f(i)$ and calculate the value of $f(i)$. Thus we can get the value of $c_i$ and $d_i$ using the value of $c_{i+1}$ and $d_{i+1}$ by considering $c_n$ and $d_n$ as the base case.
    229 
    230 We get, $c_{i} = \frac{n+(n-i)\cdot c_{i+1}}{n-(n-i)\cdot d_{i+1}}$ and $d_{i} = \frac{i}{n-(n-i) \cdot d_{i+1}}$.
    231 
    232 **Calculation**
    233 
    234 Substituting $f(i+1) = c_{i+1} + d_{i+1}\cdot f(i)$,
    235 
    236 $ \begin{align} f(i) & = 1 + \frac{i}{n} \cdot f(i-1) + \frac{n-i}{n} \cdot [c_{i+1} + d_{i+1}\cdot f(i)]\\ & = 1 + \frac{i}{n}\cdot f(i-1) + \frac{n-i}{n} \cdot c_{i+1} + \frac{n-i}{n} \cdot d_{i+1} \cdot f(i)\\ & = \frac{1+\frac{n-i}{n}\cdot c_{i+1}}{1-\frac{n-i}{n}\cdot d_{i+1}} + \frac{i}{n-(n-i) \cdot d_{i+1}}f(i-1)\\ & = \frac{n+(n-i)\cdot c_{i+1}}{n-(n-i)\cdot d_{i+1}} + \frac{i}{n-(n-i) \cdot d_{i+1}}f(i-1)\\ & = c_{i} + d_{i} \cdot f(i-1) \end{align} $
    237 
    238 So, $c_{i} = \frac{n+(n-i)\cdot c_{i+1}}{n-(n-i)\cdot d_{i+1}}$ and $d_{i} = \frac{i}{n-(n-i) \cdot d_{i+1}}$.
    239 
    240 Now, $f(i) = c_i + d_i \cdot f(i-1)$ and $f(i-1) = a_{i-1} + b_{i-1} \cdot f(i)$. By solving these two equations, we find that $f(i) = \frac{c_i+d_i \cdot a_{i-1}}{1-d_i \cdot b_{i-1}}$.
    241 
    242 Time Complexity: $\mathcal{O}(n\cdot \log m)$.
    243 
    244 **Alternative Solution**
    245 
    246 After some calculations, it can be shown that $f(1) = 2^n - 1$. Now we know $f(0) = 0$ and $f(1) = 2^n - 1$.
    247 
    248 From the relation between $f(i)$, $f(i-1)$ and $f(i-2)$, we can write $f(i) = \frac{n\cdot f(i-1) - i \cdot f(i-2) - n}{n-i+1}$.
    249 
    250 **Code**
    251 
    252 ```
    253 #include <bits/stdc++.h>
    254 using namespace std;
    255 
    256 #define mod 998244353 
    257 #define N 1000005
    258  
    259 template<int MOD>
    260 struct ModInt {
    261   unsigned x;
    262   ModInt() : x(0) { }
    263   ModInt(signed sig) : x(sig) {  }
    264   ModInt(signed long long sig) : x(sig%MOD) { }
    265   int get() const { return (int)x; }
    266   ModInt pow(ll p) { ModInt res = 1, a = *this; while (p) { if (p & 1) res *= a; a *= a; p >>= 1; } return res; }
    267  
    268   ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
    269   ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
    270   ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
    271   ModInt &operator/=(ModInt that) { return (*this) *= that.pow(MOD - 2); }
    272  
    273   ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
    274   ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
    275   ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
    276   ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
    277   bool operator<(ModInt that) const { return x < that.x; }
    278   friend ostream& operator<<(ostream &os, ModInt a) { os << a.x; return os; }
    279 };
    280 typedef ModInt<998244353> mint;
    281  
    282 mint a[N], b[N], c[N], d[N];
    283  
    284  
    285 int main(){
    286     ios::sync_with_stdio(false);
    287     cin.tie(0);
    288  
    289     int t;
    290     cin >> t;
    291     while(t--){
    292         int n;
    293         cin >> n;
    294  
    295         string s1, s2;
    296         cin >> s1 >> s2;
    297  
    298         int diff = 0;
    299         for(int i = 0; i < n; i++){
    300             diff += s1[i]!=s2[i];
    301         }
    302  
    303         c[n] = 1, d[n] = 1, a[1] = 1, b[1] = ((mint) n-1)/n;
    304  
    305         for(int i = 2; i <= n; i++){
    306             a[i] = ((mint) n + a[i-1]*i)/((mint) n - b[i-1]*i);
    307             b[i] = ((mint) n-i)/((mint) n - b[i-1]*i);
    308         }
    309  
    310         for(int i = n-1; i >= 1; i--){
    311             c[i] = ((mint) n + c[i+1]*(n-i))/((mint) n - d[i+1]*(n-i));
    312             d[i] = (mint) i / ((mint) n - d[i+1]*(n-i));
    313         }
    314  
    315         mint ans = (c[diff]+d[diff]*a[diff-1])/((mint) 1 - d[diff]*b[diff-1]);
    316  
    317         cout << ans << endl;
    318     }
    319  
    320     return 0;
    321 }
    322 ```
    323 
    324 **Alternative Code**
    325 
    326 ```
    327 #include <bits/stdc++.h>
    328 using namespace std;
    329  
    330 #define ll long long
    331  
    332 template<int MOD>
    333 struct ModInt {
    334   unsigned x;
    335   ModInt() : x(0) { }
    336   ModInt(signed sig) : x(sig) {  }
    337   ModInt(signed long long sig) : x(sig%MOD) { }
    338   int get() const { return (int)x; }
    339   ModInt pow(ll p) { ModInt res = 1, a = *this; while (p) { if (p & 1) res *= a; a *= a; p >>= 1; } return res; }
    340  
    341   ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
    342   ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
    343   ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
    344   ModInt &operator/=(ModInt that) { return (*this) *= that.pow(MOD - 2); }
    345  
    346   ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
    347   ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
    348   ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
    349   ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
    350   bool operator<(ModInt that) const { return x < that.x; }
    351   friend ostream& operator<<(ostream &os, ModInt a) { os << a.x; return os; }
    352 };
    353 typedef ModInt<998244353> mint;
    354  
    355 int main(){
    356     ios::sync_with_stdio(false);
    357     cin.tie(0);
    358     cout.tie(0);
    359  
    360     mint two = 2;
    361  
    362     int t;
    363     cin >> t;
    364     while(t--){
    365         int n;
    366         cin >> n;
    367  
    368         string a, b;
    369         cin >> a >> b;
    370  
    371         int cnt = 0;
    372         for(int i = 0; i < n; i++){
    373             if(a[i]!=b[i]) cnt++;
    374         }
    375  
    376         vector<mint> dp(n+2);
    377         dp[0] = two.pow(n);
    378         dp[1] = dp[0]-1;
    379         dp[0] = 0;
    380  
    381         for(long long i = 2; i < n; i++){
    382             mint x = i-1;
    383             x /= n;
    384             dp[i] = (dp[i-1]-x*dp[i-2]-1)*n/(n-i+1);
    385         }
    386  
    387         dp[n] = dp[n-1]+1;
    388  
    389         cout << dp[cnt] << '\n';
    390     }
    391  
    392     return 0;
    393 }
    394 ```
    395 
    396 [1778E - The Tree Has Fallen!](/contest/1778/problem/E "Codeforces Round 848 (Div. 2)")
    397 
    398 **Tutorial**
    399 
    400 Tutorial is loading...
    401 
    402 **Code**
    403 
    404 ```
    405 #include <bits/stdc++.h>
    406 using namespace std;
    407  
    408 #define ll long long
    409 #define pb push_back
    410 #define nn '\n'
    411 #define fastio std::ios_base::sync_with_stdio(false); cin.tie(NULL);
    412  
    413 const int sz = 2e5 + 10, d = 30;
    414 vector <int> g[sz], Tree[sz];
    415 int a[sz], discover_time[sz], finish_time[sz], nodeOf[sz], tim;
    416  
    417 struct BASIS {
    418     int basis[d];
    419     int sz;
    420  
    421     void init() {
    422         for(int i = 0; i < d; i++) basis[i] = 0;
    423         sz = 0;
    424     }
    425  
    426     void insertVector(int mask) {
    427         for (int i = d-1; i >= 0; i--) {
    428             if (((mask>>i)&1) == 0) continue;
    429  
    430             if (!basis[i]) {
    431                 basis[i] = mask;
    432                 ++sz;
    433                 return;
    434             }
    435             mask ^= basis[i];
    436         }
    437     }
    438  
    439     void mergeBasis(const BASIS &from) {
    440         for(int i = d-1; i >= 0; i--) {
    441             if(!from.basis[i])
    442                 continue;
    443  
    444             insertVector(from.basis[i]);
    445         }
    446     }
    447  
    448     int findMax()  {
    449         int ret = 0;
    450         for(int i = d-1; i >= 0; i--) {
    451             if(!basis[i] || (ret>>i & 1))
    452                 continue;
    453  
    454             ret ^= basis[i];
    455         }
    456         return ret;
    457     }
    458 } in[sz], out, pre[sz], suf[sz];
    459  
    460 void in_dfs(int u, int p)
    461 {
    462     in[u].insertVector(a[u]);
    463     discover_time[u] = ++tim;
    464     nodeOf[tim] = u;
    465  
    466     for(auto &v : g[u]) {
    467         if(v == p)
    468             continue;
    469  
    470         Tree[u].pb(v);
    471         in_dfs(v, u);
    472  
    473         in[u].mergeBasis(in[v]);
    474     }
    475     finish_time[u] = tim;
    476 }
    477  
    478 inline bool in_subtree(int sub_root, int v)
    479 {
    480     return discover_time[sub_root] <= discover_time[v]
    481             && finish_time[sub_root] >= finish_time[v];
    482 }
    483  
    484 int findChildOnPath(int sub_root, int v)
    485 {
    486     int lo = 0, hi = (int)Tree[sub_root].size()-1;
    487  
    488     while(lo <= hi) {
    489         int mid = lo+hi>>1, node = Tree[sub_root][mid];
    490  
    491         if(finish_time[node] < discover_time[v])
    492             lo = mid + 1;
    493         else if(discover_time[node] > discover_time[v])
    494             hi= mid - 1;
    495         else
    496             return node;
    497     }
    498 }
    499  
    500 void init(int n) {
    501  
    502     for(int i = 0; i <= n+5; i++) {
    503         g[i].clear(), Tree[i].clear();
    504         in[i].init();
    505         pre[i].init(), suf[i].init();
    506     }
    507     tim = 0;
    508 }
    509  
    510 int main()
    511 {
    512     fastio;
    513  
    514     int t;
    515     cin >> t;
    516  
    517     while(t--) {
    518         int n; cin >> n;
    519  
    520         init(n);
    521  
    522         for(int i = 1; i <= n; i++) cin >> a[i];
    523  
    524         for(int i = 1; i < n; i++) {
    525             int u, v;
    526             cin >> u >> v;
    527             g[u].pb(v); g[v].pb(u);
    528         }
    529  
    530         in_dfs(1, -1);
    531  
    532         for(int i = 1; i <= n; i++) {
    533             pre[i].insertVector(a[ nodeOf[i] ]);
    534             pre[i].mergeBasis(pre[i-1]);
    535         }
    536  
    537         for(int i = n; i >= 1; i--) {
    538             suf[i].insertVector(a[ nodeOf[i] ]);
    539             suf[i].mergeBasis(suf[i+1]);
    540         }
    541  
    542         int q; cin >> q;
    543  
    544         while(q--) {
    545             int root, v;
    546             cin >> root >> v;
    547  
    548             if(root == v) {
    549                 cout << in[1].findMax() << nn;
    550             }
    551             else if(in_subtree(v, root)) {
    552                 int child = findChildOnPath(v, root);
    553  
    554                 out.init();
    555                 out.mergeBasis(pre[discover_time[child]-1]);
    556                 out.mergeBasis(suf[finish_time[child]+1]);
    557                 cout << out.findMax() << nn;
    558             }
    559             else
    560                 cout << in[v].findMax() << nn;
    561         }
    562     }
    563  
    564     return 0;
    565 }
    566 ```
    567 
    568 [1778F - Maximizing Root](/contest/1778/problem/F "Codeforces Round 848 (Div. 2)")
    569 
    570 **Tutorial**
    571 
    572 Tutorial is loading...
    573 
    574 **Code**
    575 
    576 ```
    577 #include <bits/stdc++.h>
    578 using namespace std;
    579  
    580 const int N = 100005;
    581 const int mod = 998244353;
    582  
    583 int val[N];
    584 vector<int> g[N];
    585 vector<int> divisor[N];
    586 int subtree_gcd[N], par[N];
    587  
    588 int dp[N][1003];
    589 int gcdd[1003][1003];
    590  
    591 inline long long ___gcd(long long a, long long b){
    592     if(gcdd[a][b]) return gcdd[a][b];
    593  
    594     return gcdd[a][b] = __gcd(a, b);
    595 }
    596  
    597 inline long long lcm(long long a, long long b){
    598     return (a/___gcd(a, b))*b;
    599 }
    600  
    601 void dfs(int u, int p){
    602     par[u] = p;
    603     subtree_gcd[u] = val[u];
    604     for(int v: g[u]){
    605         if(v==p) continue;
    606         dfs(v, u);
    607         subtree_gcd[u] = ___gcd(subtree_gcd[u], subtree_gcd[v]);
    608     }
    609 }
    610  
    611  
    612 int solve(int u, int d, int p){
    613     if(subtree_gcd[u]%d==0) return 0;
    614     if((val[u]*val[u])%d) return (1<<30);
    615  
    616  
    617     if(dp[u][d]!=-1) return dp[u][d];
    618     
    619     long long req = d/___gcd(d, subtree_gcd[u]);
    620  
    621     long long res = (1<<30);
    622     for(int div: divisor[val[u]]){
    623         if((val[u]*div)%d==0 && d%div==0){
    624             long long r = 1;
    625             for(int v: g[u]){
    626                 if(v==p) continue;
    627                 r += solve(v, lcm(d/div, div), u);
    628             }
    629             res = min(res, r);
    630         }
    631     }
    632  
    633     return dp[u][d] = min(res, (1LL<<30));
    634 }
    635  
    636 int main(){
    637     ios::sync_with_stdio(false);
    638     cin.tie(nullptr);
    639  
    640     for(int i = 2; i < 1001; i++){
    641         for(int j = i; j < 1001; j+=i){
    642             divisor[j].push_back(i);
    643         }
    644     }
    645  
    646     int t;
    647     cin >> t;
    648  
    649     while(t--){
    650         int n, k;
    651         cin >> n >> k;
    652  
    653         for(int i = 0; i <= n; i++){
    654             g[i].clear();
    655         }
    656  
    657         for(int i = 1; i <= n; i++){
    658             cin >> val[i];
    659         }
    660         
    661         for(int i = 0; i <= n; i++){
    662             for(int d: divisor[val[1]]){
    663                 dp[i][d] = -1;
    664             }
    665         }
    666  
    667         for(int i = 0; i < n-1; i++){
    668             int u, v;
    669             cin >> u >> v;
    670             g[u].push_back(v);
    671             g[v].push_back(u);
    672         }
    673  
    674         dfs(1, 0);
    675  
    676         int ans = val[1];
    677  
    678         for(int d: divisor[val[1]]){
    679             int req = 0;
    680             int f = 1;
    681             for(int v: g[1]){
    682                 int x = solve(v, d, par[v]);
    683                 if(x>n) f = 0;
    684                 req += x;
    685             }
    686  
    687             if(!f) continue;
    688  
    689             req++;
    690             if(req<=k){
    691                 ans = max(ans, val[1]*d);
    692             }
    693         }
    694  
    695         cout << ans << "\n";
    696     }
    697     
    698     return 0;
    699 }
    700 ```