codeforces-scrape

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

2236.md (28716B)


      1 Source: https://codeforces.com/blog/entry/154496
      2 
      3 [2236A - Games on the Train](/contest/2236/problem/A "Codeforces Round 1103 (Div. 3)")
      4 
      5 Idea: [arsen1y](/profile/arsen1y "Specialist arsen1y")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (arsen1y)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 #define int long long
     16  
     17 using namespace std;
     18  
     19 const int INF = (int) 1e18;
     20  
     21 int32_t main() {
     22     std::ios::sync_with_stdio(false);
     23     cin.tie(NULL);
     24     cout.tie(NULL);
     25  
     26     int _;
     27     cin >> _;
     28  
     29     while (_--) {
     30         int n;
     31         cin >> n;
     32  
     33         vector <int> a(n);
     34         int mx = -INF;
     35         int mn = INF;
     36         for (int i = 0; i < n; ++i) {
     37             cin >> a[i];
     38             mx = max(mx, a[i]);
     39             mn = min(mn, a[i]);
     40         }
     41  
     42         cout << mx - mn + 1 << "\n";
     43     }
     44  
     45     return 0;
     46 }
     47 ```
     48 
     49 [2236B - Tatar TV Show](/contest/2236/problem/B "Codeforces Round 1103 (Div. 3)")
     50 
     51 Idea: [eyfxrby](/profile/eyfxrby "Expert eyfxrby")
     52 
     53 **Hint**
     54 
     55 Try to find a property that does not change during operations.
     56 
     57 **Tutorial**
     58 
     59 Tutorial is loading...
     60 
     61 **Solution (eyfxrby)**
     62 
     63 ```
     64 #include <bits/stdc++.h>
     65 using namespace std;
     66  
     67 int main() {
     68     int t;
     69     cin >> t;
     70     while (t--) {
     71         int n, k; cin >> n >> k;
     72         string s; cin >> s;
     73         vector<int> cnt(k, 0);
     74         for (int i = 0; i < n; i++) cnt[i % k] += s[i] - '0';
     75         bool ok = true;
     76         for (int r = 0; r < k; r++) {
     77             if (cnt[r] % 2) {
     78                 ok = false;
     79                 break;
     80             }
     81         }
     82         cout << (ok ? "YES" : "NO") << '\n';
     83     }
     84 }
     85 ```
     86 
     87 [2236C - Omsk Programmers](/contest/2236/problem/C "Codeforces Round 1103 (Div. 3)")
     88 
     89 Idea: [arsen1y](/profile/arsen1y "Specialist arsen1y")
     90 
     91 **Hint**
     92 
     93 It can be shown that it is advantageous to do only divisions first, and then only additions.
     94 
     95 **Tutorial**
     96 
     97 Tutorial is loading...
     98 
     99 **Solution (arsen1y)**
    100 
    101 ```
    102 #include <bits/stdc++.h>
    103 #define int long long
    104  
    105 using namespace std;
    106  
    107 const int INF = (int) 1e18;
    108  
    109 int32_t main() {
    110     int _;
    111     cin >> _;
    112  
    113     while (_--) {
    114         int a, b, x;
    115         cin >> a >> b >> x;
    116  
    117         int ans = INF;
    118         int i = 0;
    119         while (a != b) {
    120             if (b > a) {
    121                 swap(a, b);
    122             }
    123  
    124             ans = min(ans, abs(a - b) + i);
    125             a /= x;
    126             i++;
    127         }
    128  
    129         ans = min(ans, i);
    130  
    131         cout << ans << "\n";
    132     }
    133  
    134     return 0;
    135 }
    136 ```
    137 
    138 [2236D - Brand New Tatar TV Show](/contest/2236/problem/D "Codeforces Round 1103 (Div. 3)")
    139 
    140 Idea: [dvb1r](/profile/dvb1r "Candidate Master dvb1r")
    141 
    142 **Hint 1**
    143 
    144 What happens if Arseny chooses the maximum of the array as his first move?
    145 
    146 **Answer**
    147 
    148 If the count of maximum is odd, then Dabir wins, otherwise Egor wins.
    149 
    150 **Hint 2**
    151 
    152 Try to look at the second maximum.
    153 
    154 **Tutorial**
    155 
    156 Tutorial is loading...
    157 
    158 **Solution (dvb1r)**
    159 
    160 ```
    161 #include <bits/stdc++.h>
    162 
    163 using namespace std;
    164 void solve();
    165 
    166 int main() {
    167     int t; cin >> t;
    168     while (t--) solve();
    169     return 0;
    170 }
    171 
    172 void solve() {
    173     int n, k; cin >> n >> k;
    174     vector<int> A(n);
    175     for (auto& x : A) cin >> x;
    176     sort(A.begin(), A.end());
    177     vector<pair<int, int>> a = {{A[0], 1}};
    178     for (int i = 1; i < n; ++i) {
    179         if (A[i] == A[i - 1]) a.back().second++;
    180         else a.emplace_back(A[i], 1);
    181     }
    182 
    183     while (a.size() > 0) {
    184         n = a.size();
    185         if (a[n - 1].second % 2 == 0) {
    186             cout << "YES\n";
    187             return;
    188         }
    189         if (n == 1) {
    190             cout << "NO\n";
    191             return;
    192         }
    193         if (a[n - 1].first - a[n - 2].first <= k) {
    194             cout << "YES\n";
    195             return;
    196         }
    197         a.pop_back();
    198     }
    199 }
    200 ```
    201 
    202 [2236E - Friendly Gifts](/contest/2236/problem/E "Codeforces Round 1103 (Div. 3)")
    203 
    204 Idea: [arsen1y](/profile/arsen1y "Specialist arsen1y")
    205 
    206 **Hint 1**
    207 
    208 The cut segments of the array do not need to be checked for non-intersection.
    209 
    210 **Hint 2**
    211 
    212 Try to save information about all the good segments, and only then find the answer.
    213 
    214 **Tutorial**
    215 
    216 Tutorial is loading...
    217 
    218 **Solution (dvb1r)**
    219 
    220 ```
    221 #include <bits/stdc++.h>
    222 
    223 using namespace std;
    224 void solve();
    225 
    226 int main() {
    227     int t = 1; cin >> t;
    228     while (t--) solve();
    229     return 0;
    230 }
    231 
    232 void solve() {
    233     int n; cin >> n;
    234     vector<int> a(n);
    235     for (auto& x : a) cin >> x, --x;
    236     vector<vector<bool>> able(n, vector<bool>(n));
    237     for (int i = 0; i < n; ++i) {
    238         vector<int> us(n);
    239         int mn = a[i], mx = a[i];
    240         for (int j = i; j < n; ++j) {
    241             if (us[a[j]]) break;
    242             us[a[j]] = 1;
    243             mn = min(mn, a[j]), mx = max(mx, a[j]);
    244             if (mx - mn == j - i) able[mn][mx] = 1;
    245         }
    246     }
    247     
    248     for (int ans = n; ans > 0; --ans) {
    249         for (int i = 0; i + 2 * ans <= n; ++i) {
    250             if (able[i][i + ans - 1] && able[i + ans][i + 2 * ans - 1]) {
    251                 cout << ans << '\n';
    252                 return;
    253             }
    254         }
    255     }
    256     cout << "0\n";
    257 }
    258 ```
    259 
    260 [2236F1 - Elections in Saransk (easy version)](/contest/2236/problem/F1 "Codeforces Round 1103 (Div. 3)")
    261 
    262 Idea: [eyfxrby](/profile/eyfxrby "Expert eyfxrby")
    263 
    264 **Hint 1**
    265 
    266 What can we say about $gcd(p_i, p_j)$ for any pair $(i, j)$?
    267 
    268 **Answer**
    269 
    270 $gcd(p_i, p_j) = 1$.
    271 
    272 **Hint 2**
    273 
    274 Let's take a simple number $pr$. How many elements of the array $p$ can be divisible by this $pr$?
    275 
    276 **Answer**
    277 
    278 No more than one.
    279 
    280 **Tutorial**
    281 
    282 Tutorial is loading...
    283 
    284 **Solution**
    285 
    286 ```
    287 #include <bits/stdc++.h>
    288 #include <ext/pb_ds/assoc_container.hpp>
    289 #include <bits/stdc++.h>
    290 #include <immintrin.h>
    291  
    292 using namespace __gnu_pbds;
    293 using namespace std;
    294  
    295 #define eps 1e-7
    296 #define MOD2 119 * (1ll << 23) + 1
    297 #define int long long
    298 #define mp make_pair
    299 #define pll pair <long long, long long>
    300 #define next return
    301 #define skip continue
    302 #define all(a) a.begin(), a.end()
    303 #define rall(a) a.rbegin(), a.rend()
    304 #define f first
    305 #define max_of max_element
    306 #define min_of min_element
    307 #define s second
    308  
    309 // const int MAX_MEM = 4e8;
    310 // int mpos = 0;
    311 // alignas(long long) char mem[MAX_MEM];
    312 // inline void * operator new(size_t n) {
    313 //     if (n & 7) n += 8 - (n & 7);
    314 //     char *res = mem + mpos;
    315 //     mpos += n;
    316 //     return (void *)res;
    317 // }
    318 // void operator delete(void *) {}
    319  
    320 int scan() {
    321     int x;
    322     cin >> x;
    323     return x;
    324 }
    325  
    326 string read() {
    327     string s;
    328     cin >> s;
    329     return s;
    330 }
    331  
    332 const int N = 1e6 + 5, MOD = 1e9 + 7;
    333 int lp[N], a[N], x, n, v[101];
    334 vector<int> pr, divs[N];
    335  
    336 int bin_pow(int x, int n) {
    337     int res = 1;
    338     while (n) {
    339         if ((n & 1)) res = res * x % MOD;
    340         n >>= 1;
    341         x = x * x % MOD;
    342     }
    343     return res;
    344 }
    345  
    346 int solveF1_AUTHOR() {
    347     map <int, int> cnt;
    348     int cur_x;
    349     int mx = *max_element(a + 1, a + n + 1);
    350     set <int> setik;
    351     for (int i = 1; i <= n; i++) {
    352         int val = a[i];
    353         cur_x = val;
    354         while (cur_x > 1) {
    355             setik.insert(lp[cur_x]);
    356             cnt[lp[cur_x]]++;
    357             cur_x /= lp[cur_x];
    358         }
    359     }
    360     int ans = 1;
    361     for (auto prime: setik) {
    362         int sum = 1;
    363         //cout << prime << ' ' << cnt[prime] << '\n';
    364         ans = (ans * (cnt[prime] + 1)) % MOD;
    365     }
    366     return ans;
    367 }
    368  
    369  
    370 int32_t main() {
    371     lp[1] = 1;
    372     for (int i = 2; i < N; i++) {
    373         if (lp[i] == 0) {
    374             pr.push_back(i);
    375             lp[i] = i;
    376         }
    377         for (int j = 0; j < (int) pr.size() && pr[j] <= lp[i] && i * pr[j] < N; j++) {
    378             lp[i * pr[j]] = pr[j];
    379         }
    380     }
    381     int t = scan();
    382     while (t--) {
    383         n = scan(); x = scan();
    384         for (int i = 1; i <= n; i++) a[i] = scan();
    385         cout << solveF1_AUTHOR() << '\n';
    386     }
    387 }
    388 ```
    389 
    390 [2236F2 - Elections in Saransk (hard version)](/contest/2236/problem/F2 "Codeforces Round 1103 (Div. 3)")
    391 
    392 Idea: [eyfxrby](/profile/eyfxrby "Expert eyfxrby")
    393 
    394 **Hint 1**
    395 
    396 Try to fix the prime number $pr$. How can we transform the condition of the perfect array $p$ using $v_{pr}$?
    397 
    398 **Answer**
    399 
    400 $x \cdot lcm(p_1, p_2, \ldots, p_n) = p_1 \cdot p_2 \cdot \ldots \cdot p_n \lt = \gt max(v_{pr}(p_i)) + v_{pr}(x) = \sum(v_{pr}(p_i)$)
    401 
    402 **Hint 2**
    403 
    404 Consider what a simple $pr$ might be. What types of $pr$ can it be classified into?
    405 
    406 **Answer**
    407 
    408 $x$ is divisible by $pr$, and $x$ is not divisible by $pr$.
    409 
    410 **Hint 3**
    411 
    412 Think about how to solve each of the cases in hint 2.
    413 
    414 **Tutorial**
    415 
    416 Tutorial is loading...
    417 
    418 **Solution 1 (eyfxrby)**
    419 
    420 ```
    421 #include <bits/stdc++.h>
    422 #include <ext/pb_ds/assoc_container.hpp>
    423 #include <bits/stdc++.h>
    424 #include <immintrin.h>
    425 
    426 using namespace __gnu_pbds;
    427 using namespace std;
    428 
    429 #define eps 1e-7
    430 #define MOD2 119 * (1ll << 23) + 1
    431 #define int long long
    432 #define mp make_pair
    433 #define pll pair <long long, long long>
    434 #define next return
    435 #define skip continue
    436 #define all(a) a.begin(), a.end()
    437 #define rall(a) a.rbegin(), a.rend()
    438 #define f first
    439 #define max_of max_element
    440 #define min_of min_element
    441 #define s second
    442 
    443 int scan() {
    444     int x;
    445     cin >> x;
    446     return x;
    447 }
    448 
    449 string read() {
    450     string s;
    451     cin >> s;
    452     return s;
    453 }
    454 
    455 const int N = 1e6 + 2, MOD = 1e9 + 7;
    456 int lp[N], a[N], x, n, v[N];
    457 vector<int> pr, divs[N];
    458 
    459 int MAX_V = -1E9;
    460 
    461 int solve_for_prime(int vp) {
    462     int mx_pref = 0;
    463     int S = 0;
    464     for (int i = 1; i <= n; i++) S += v[i];
    465     S = min(S, 36ll);
    466     int dp[MAX_V + 1][MAX_V + S + 2];
    467     int old_pref_sum[MAX_V + 1][MAX_V + S + 2];
    468     int old_pref_sum2[MAX_V + 1][MAX_V + S + 2];
    469     memset(dp, 0, sizeof dp);
    470     memset(old_pref_sum, 0, sizeof old_pref_sum);
    471     memset(old_pref_sum2, 0, sizeof old_pref_sum2);
    472     int sum = 0;
    473     dp[0][0] = 1;
    474     for (int i = 0; i <= n; i++) {
    475         for (int sum_vp = 0; sum_vp <= S && i > 0; sum_vp++) {
    476             for (int new_max = 1; new_max <= min(sum_vp, v[i]); new_max++) {
    477                 dp[new_max][sum_vp] += old_pref_sum2[new_max - 1][sum_vp - new_max];
    478                 if (dp[new_max][sum_vp] >= MOD) dp[new_max][sum_vp] -= MOD;
    479             }
    480             for (int old_max = 0; old_max <= min(mx_pref, sum_vp); old_max++) {
    481                 dp[old_max][sum_vp] += (old_pref_sum[old_max][sum_vp] + MOD - (sum_vp - min(old_max, v[i]) - 1 < 0 ? 0 :
    482                                                                               old_pref_sum[old_max][sum_vp - min(old_max, v[i]) - 1])) % MOD;
    483                 //if (dp[old_max][sum_vp] >= MOD) dp[old_max][sum_vp] -= MOD;
    484 
    485             }
    486         }
    487         for (int old_max = 0; old_max <= MAX_V; old_max++) {
    488             for (int j = 0; j <= MAX_V + S; j++) {
    489                 old_pref_sum[old_max][j] = 0;
    490                 old_pref_sum[old_max][j] = (!j ? dp[old_max][j] : old_pref_sum[old_max][j - 1] + dp[old_max][j]);
    491                 if (old_pref_sum[old_max][j] >= MOD) old_pref_sum[old_max][j] -= MOD;
    492             }
    493         }
    494         for (int j = 0; j <= MAX_V + S; j++) {
    495             for (int old_max = 0; old_max <= MAX_V; old_max++) {
    496                 old_pref_sum2[old_max][j] = 0;
    497                 old_pref_sum2[old_max][j] = (!old_max ? dp[old_max][j] : old_pref_sum2[old_max - 1][j] + dp[old_max][j]);
    498                 if (old_pref_sum2[old_max][j] >= MOD) old_pref_sum2[old_max][j] -= MOD;
    499                 if(i != n) dp[old_max][j] = 0;
    500             }
    501         }
    502         mx_pref = max(mx_pref, v[i]);
    503     }
    504     int ret = 0;
    505     for (int mx = 1; vp + mx <= S && mx <= MAX_V; mx++) {
    506         ret = (ret + dp[mx][vp + mx]);
    507         if (ret >= MOD) ret -= MOD;
    508     }
    509     return ret;
    510 }
    511 
    512 int solveF2_AUTHOR() {
    513     map<int, int> cnt_pr;
    514     int cur_x = x;
    515     while (cur_x > 1) {
    516         int next_div = lp[cur_x];
    517         cnt_pr[next_div]++;
    518         cur_x /= next_div;
    519     }
    520     int ans = 1;
    521     for (auto [prime, cnt]: cnt_pr) {
    522         MAX_V = -1e9;
    523         for (int i = 1; i <= n; i++) {
    524             cur_x = a[i];
    525             v[i] = 0;
    526             while (cur_x % prime == 0) {
    527                 v[i]++;
    528                 cur_x /= prime;
    529             }
    530             MAX_V = max(MAX_V, v[i]);
    531         }
    532         ans = (ans * solve_for_prime(cnt)) % MOD;
    533     }
    534     map <int, int> cnt;
    535     int mx = *max_element(a + 1, a + n + 1);
    536     set <int> setik;
    537     for (int i = 1; i <= n; i++) {
    538         int val = a[i];
    539         cur_x = val;
    540         while (cur_x > 1) {
    541             cnt[lp[cur_x]]++;
    542             setik.insert(lp[cur_x]);
    543             cur_x /= lp[cur_x];
    544         }
    545     }
    546     for (auto prime: setik) {
    547         //if (2 * prime > mx) break;
    548         int sum = 1;
    549         if (x % prime != 0) ans = (ans * (cnt[prime] + 1)) % MOD;
    550     }
    551     return ans;
    552 }
    553 
    554 int32_t main() {
    555     for (int i = 2; i < N; i++) {
    556         if (lp[i] == 0) {
    557             pr.push_back(i);
    558             lp[i] = i;
    559         }
    560         for (int j = 0; j < (int) pr.size() && pr[j] <= lp[i] && i * pr[j] < N; j++) {
    561             lp[i * pr[j]] = pr[j];
    562         }
    563     }
    564     int t = scan();
    565     while (t--) {
    566         n = scan(), x = scan();
    567         for (int i = 1; i <= n; i++) a[i] = scan();
    568         cout << solveF2_AUTHOR() << '\n';
    569     }
    570 }
    571 ```
    572 
    573 **Solution 2 (Treks)**
    574 
    575 ```
    576 //#pragma GCC optimize("Ofast")
    577 //#pragma GCC optimize("O3,unroll-loops")
    578 
    579 #include <bits/stdc++.h>
    580 #include <experimental/random>
    581 #include <ext/pb_ds/assoc_container.hpp>
    582 
    583 using namespace std;
    584 using namespace __gnu_pbds;
    585 
    586 using ll = long long;
    587 using ld = long double;
    588 using ordered_set = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;
    589 using str = string;
    590 const ll INF = 1e18, MOD = 1e9 + 7;
    591 template<class T> using pq_min = priority_queue<T, vector<T>, greater<T>>;
    592 template<class T> using pq_max = priority_queue<T, vector<T>, less<T>>;
    593 #define int long long
    594 
    595 void solve();
    596 
    597 vector<int> P;
    598 const int Mx = 1e4;
    599 
    600 signed main() {
    601     vector<bool> us(Mx);
    602     for (int i = 2; i < Mx; ++i) {
    603         if (!us[i]) {
    604             P.push_back(i);
    605             for (int j = i * i; j < Mx; j += i) {
    606                 us[j] = true;
    607             }
    608         }
    609     }
    610 #ifdef LOCAL
    611     freopen("input.txt", "r", stdin);
    612     freopen("output.txt", "w", stdout);
    613 #endif
    614     ios::sync_with_stdio(false);
    615     cin.tie(0);
    616     cout.tie(0);
    617     ll q = 1;
    618     cin >> q;
    619     while (q--) {
    620         solve();
    621         cout << "\n";
    622     }
    623 }
    624 
    625 void solve() {
    626     int n, x;
    627     cin >> n >> x;
    628     map<int, int> cnt;
    629     for (auto w: P) {
    630         if (w * w > x) {
    631             break;
    632         }
    633         while (x % w == 0) {
    634             x /= w;
    635             cnt[w]++;
    636         }
    637     }
    638     if (x > 1) {
    639         cnt[x]++;
    640     }
    641     vector<int> a(n);
    642     for (int i = 0; i < n; ++i) {
    643         cin >> a[i];
    644     }
    645     map<int, vector<int>> w1;
    646     for (int i = 0; i < n; ++i) {
    647         for (auto w: P) {
    648             if (w * w > a[i]) {
    649                 break;
    650             }
    651             int sum = 0;
    652             while (a[i] % w == 0) {
    653                 a[i] /= w;
    654                 sum++;
    655             }
    656             if (sum > 0) {
    657                 w1[w].push_back(sum);
    658             }
    659         }
    660         if (a[i] > 1) {
    661             w1[a[i]].push_back(1);
    662         }
    663     }
    664     int Ans = 1;
    665     for (auto [id, e]: w1) {
    666         int mx = 0;
    667         for (auto s: e) {
    668             mx = max(mx, s);
    669         }
    670         vector<vector<int>> dp(cnt[id] + 1, vector<int>(mx + 1));
    671         dp[0][0] = 1;
    672         for (auto w: e) {
    673             vector<vector<int>> dp1(cnt[id] + 1, vector<int>(mx + 1));
    674             for (int i = 0; i <= w; ++i) {
    675                 for (int j = 0; j <= cnt[id]; ++j) {
    676                     for (int k = 0; k <= mx; ++k) {
    677                         if (j + min(i, k) <= cnt[id]) {
    678                             dp1[j + min(i, k)][max(i, k)] += dp[j][k];
    679                             dp1[j + min(i, k)][max(i, k)] %= MOD;
    680                         }
    681                     }
    682                 }
    683             }
    684             swap(dp, dp1);
    685         }
    686         int s = 0;
    687         for (int i = 0; i <= mx; ++i) {
    688             s += dp[cnt[id]][i];
    689         }
    690         s %= MOD;
    691         Ans *= s;
    692         Ans %= MOD;
    693         cnt[id] = 0;
    694     }
    695     for (auto s: cnt) {
    696         if (s.second > 0) {
    697             Ans = 0;
    698         }
    699     }
    700     cout << Ans;
    701 }
    702 ```
    703 
    704 [2236G - Criterion in Burlandia](/contest/2236/problem/G "Codeforces Round 1103 (Div. 3)")
    705 
    706 Idea: [dvb1r](/profile/dvb1r "Candidate Master dvb1r")
    707 
    708 **Hint 1**
    709 
    710 In fact, the XOR of non-negative numbers is always less or equal their sum, and you can think about why.
    711 
    712 **Hint 2**
    713 
    714 Using the fact that the XOR of a set of numbers is equal to the sum of those numbers, how many non-zero numbers can there be in this set?
    715 
    716 **Answer**
    717 
    718 No more than $log(A)$, since each bit must occur at most once.
    719 
    720 **Hint 3**
    721 
    722 For each vertex, pre-calculate the closest ancestor on the vertical path that violates the good segment condition.
    723 
    724 **Hint 4**
    725 
    726 Reduce the problem to a path of length at most $2 * log(A)$, and calculate the rest using the pre-calculation from hint 3.
    727 
    728 **Tutorial**
    729 
    730 Tutorial is loading...
    731 
    732 **Solution 1 (dvb1r)**
    733 
    734 ```
    735 #include <bits/stdc++.h>
    736  
    737 using namespace std;
    738 using ll = long long;
    739 void solve();
    740  
    741 int main() {
    742     int t = 1;
    743     cin >> t;
    744     while (t --> 0) solve();
    745     return 0;
    746 }
    747  
    748 struct Graph {
    749     vector<int> tin, tout, d;
    750     vector<vector<pair<int, ll>>> up;
    751  
    752     int timer;
    753  
    754     void dfs(int v, const vector<vector<int>>& g, const vector<int>& arr, int p = -1) {
    755         tin[v] = timer++;
    756         up[0][v] = {p, arr[v]};
    757         for (int l = 1; l < 20; ++l) {
    758             if (up[l - 1][v].first == -1) {
    759                 up[l][v] = {-1, 0};
    760                 continue;
    761             }
    762             up[l][v].first = up[l - 1][up[l - 1][v].first].first;
    763             up[l][v].second = up[l - 1][up[l - 1][v].first].second + up[l - 1][v].second;
    764         }
    765         for (int u : g[v]) {
    766             if (u == p) continue;
    767             d[u] = d[v] + 1;
    768             dfs(u, g, arr, v);
    769         }
    770         tout[v] = timer;
    771     }
    772  
    773     Graph(const vector<vector<int>>& g, const vector<int>& a) : tin(g.size()), tout(g.size()), d(g.size()), up(20, vector<pair<int, ll>>(g.size())) {
    774         timer = 0;
    775         dfs(0, g, a);
    776     }
    777  
    778     bool anc(int p, int v) {
    779         return tin[p] <= tin[v] && tout[p] >= tout[v];
    780     }
    781  
    782     int getLenVertical(int u, int v) {
    783         if (!anc(u, v)) swap(u, v);
    784         assert(anc(u, v));
    785         return d[v] - d[u] - 1;
    786     }
    787  
    788     pair<int, ll> LA(int v, int k) {
    789         if (k <= 0) return {v, 0};
    790         ll sum = 0;
    791         for (int i = 0; i < 20; ++i) {
    792             if (k >> i & 1) sum += up[i][v].second, v = up[i][v].first;
    793         }
    794         return {v, sum};
    795     }
    796  
    797     int LCA(int u, int v) {
    798         if (anc(u, v)) return u;
    799         for (int l = 19; l >= 0; --l) {
    800             if (up[l][u].first == -1 || anc(up[l][u].first, v)) continue;
    801             u = up[l][u].first;
    802         }
    803         return up[0][u].first;
    804     }
    805  
    806     bool lower(int a, int b) {
    807         return tin[a] < tin[b];
    808     }
    809 };
    810  
    811 ll sum(int r) { return r * 1ll * (r + 1) / 2; }
    812  
    813 ll sumSeg(int l, int r) {
    814     return sum(r) - sum(l - 1);
    815 }
    816  
    817 void solve() {
    818     int n, q; cin >> n >> q;
    819     vector<int> a(n);
    820     for (int i = 0; i < n; ++i) cin >> a[i];
    821     vector<vector<int>> g(n);
    822     for (int i = 1; i < n; ++i) {
    823         int u, v; cin >> u >> v;
    824         --u, --v;
    825         g[u].emplace_back(v);
    826         g[v].emplace_back(u);
    827     }
    828     vector<int> parent(n), d(n);
    829     auto dfs = [&](auto& self, int v, int p = -1) -> void {
    830         parent[v] = p;
    831         for (int u : g[v]) {
    832             if (u == p) continue;
    833             d[u] = d[v] + 1;
    834             self(self, u, v);
    835         }
    836     };
    837     dfs(dfs, 0);
    838  
    839     vector<int> compressed_parent = parent;
    840     vector<vector<int>> cG(n);
    841     for (int v = 0; v < n; ++v) {
    842         vector<int> path;
    843         while (compressed_parent[v] > 0 && a[compressed_parent[v]] == 0) {
    844             path.emplace_back(compressed_parent[v]);
    845             compressed_parent[v] = compressed_parent[compressed_parent[v]];
    846         }
    847         for (auto& x : path) compressed_parent[x] = compressed_parent[v];
    848         if (a[v] == 0 || !v) continue;
    849         cG[compressed_parent[v]].emplace_back(v);
    850     }
    851  
    852     vector<int> next_collision(n), sum_collision(n);
    853     for (int v = 0; v < n; ++v) {
    854         if (!a[v]) continue;
    855         next_collision[v] = v;
    856         int xr = a[v], sm = a[v];
    857         while (xr == sm && next_collision[v] > -1) {
    858             next_collision[v] = compressed_parent[next_collision[v]];
    859             if (next_collision[v] == -1) break;
    860             xr ^= a[next_collision[v]];
    861             sm += a[next_collision[v]];
    862         }
    863     }
    864  
    865     for (int v = 0; v < n; ++v) {
    866         if (!a[v]) {
    867             if (!v) next_collision[v] = -1;
    868             else next_collision[v] = next_collision[compressed_parent[v]];
    869         }
    870         sum_collision[v] = d[v];
    871         if (next_collision[v] > -1) sum_collision[v] -= d[next_collision[v]];
    872         else sum_collision[v]++;
    873     }
    874  
    875     Graph def(g, sum_collision);
    876     Graph compressed(cG, sum_collision);
    877  
    878     while (q--) {
    879         int u, v; cin >> u >> v;
    880         --u, --v;
    881         if (def.lower(v, u)) swap(u, v);
    882         int z = def.LCA(u, v);
    883  
    884         int cv = (a[v] || !v ? v : compressed_parent[v]), cu = (a[u] || !u ? u : compressed_parent[u]), cz = (a[z] || !z ? z : compressed_parent[z]);
    885  
    886         ll ans = 0;
    887  
    888         vector<int> L, R, Lspaces = {0}, Rspaces = {0};
    889  
    890         if (compressed.d[cv] > compressed.d[cz] + 23) {
    891             int unt = compressed.LA(cv, compressed.d[cv] - (compressed.d[cz] + 23)).first;
    892             auto [to, sm] = def.LA(v, d[v] - d[unt]);
    893             ans += sm, v = to;
    894         }
    895  
    896         if (compressed.d[cu] > compressed.d[cz] + 23) {
    897             int unt = compressed.LA(cu, compressed.d[cu] - (compressed.d[cz] + 23)).first;
    898             auto [to, sm] = def.LA(u, d[u] - d[unt]);
    899             ans += sm, u = to;
    900         }
    901  
    902         while (u != z) {
    903             int to = compressed_parent[u];
    904             if (def.anc(to, z)) to = z;
    905             L.emplace_back(u);
    906             Lspaces.emplace_back(def.getLenVertical(u, to));
    907             u = to;
    908         }
    909         while (v != z) {
    910             int to = compressed_parent[v];
    911             if (def.anc(to, z)) to = z;
    912             R.emplace_back(v);
    913             Rspaces.emplace_back(def.getLenVertical(v, to));
    914             v = to;
    915         }
    916         L.emplace_back(z);
    917         std::reverse(R.begin(), R.end());
    918         std::reverse(Rspaces.begin(), Rspaces.end());
    919         for (auto& x : R) L.emplace_back(x);
    920         for (auto& x : Rspaces) Lspaces.emplace_back(x);
    921         int j = 0, xr = 0, sum = 0;
    922         ll cnt = 0;
    923         for (int i = 0; i < L.size(); ++i) {
    924             while (j < L.size() && xr == sum) {
    925                 xr ^= a[L[j]], sum += a[L[j]];
    926                 cnt += Lspaces[j] + 1;
    927                 j++;
    928             }
    929             if (xr != sum) cnt--;
    930             ans += sumSeg(cnt - Lspaces[i], cnt);
    931             if (xr != sum) cnt++;
    932             xr ^= a[L[i]], sum -= a[L[i]];
    933             cnt -= Lspaces[i] + 1;
    934         }
    935         cout << ans << '\n';
    936     }
    937 }
    938 ```
    939 
    940 **Solution 2 (Treks)**
    941 
    942 ```
    943 //#pragma GCC optimize("Ofast")
    944 //#pragma GCC optimize("O3,unroll-loops")
    945 
    946 #include <bits/stdc++.h>
    947 #include <experimental/random>
    948 #include <ext/pb_ds/assoc_container.hpp>
    949 
    950 using namespace std;
    951 using namespace __gnu_pbds;
    952 
    953 using ll = long long;
    954 using ld = long double;
    955 using ordered_set = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;
    956 using str = string;
    957 const ll INF = 1e18, MOD = 1e9 + 7;
    958 template<class T> using pq_min = priority_queue<T, vector<T>, greater<T>>;
    959 template<class T> using pq_max = priority_queue<T, vector<T>, less<T>>;
    960 #define int long long
    961 
    962 void solve();
    963 
    964 signed main() {
    965 #ifdef LOCAL
    966     freopen("input.txt", "r", stdin);
    967     freopen("output.txt", "w", stdout);
    968 #endif
    969     ios::sync_with_stdio(false);
    970     cin.tie(0);
    971     cout.tie(0);
    972     ll q = 1;
    973     cin >> q;
    974     while (q--) {
    975         solve();
    976         //cout << "\n";
    977     }
    978 }
    979 
    980 vector<vector<int>> g;
    981 vector<int> a;
    982 int h;
    983 vector<bool> us;
    984 int cnt1;
    985 vector<int> T;
    986 
    987 void dfs1(int v, int pr) {
    988     T.push_back(v);
    989     cnt1++;
    990     for (auto to: g[v]) {
    991         if (to != pr && !us[to]) {
    992             dfs1(to, v);
    993         }
    994     }
    995 }
    996 
    997 int dfs(int v, int pr) {
    998     bool p = true;
    999     int cnt = 1;
   1000     for (auto to: g[v]) {
   1001         if (to != pr && !us[to]) {
   1002             auto u = dfs(to, v);
   1003             if (u > cnt1 / 2) {
   1004                 p = false;
   1005             }
   1006             cnt += u;
   1007         }
   1008     }
   1009     if (p && (cnt1 &mdash; cnt) <= cnt1 / 2) {
   1010         h = v;
   1011     }
   1012     return cnt;
   1013 }
   1014 
   1015 int E = 0;
   1016 
   1017 vector<int> ans;
   1018 vector<vector<int>> mn;
   1019 vector<int> col;
   1020 vector<int> sz;
   1021 vector<int> W;
   1022 
   1023 void dfs(int v, int pr, vector<int> s, int an, int o, int mx) {
   1024     sz[v] = o;
   1025     col[v] = E;
   1026     W[v] = W[pr];
   1027     for (int i = 0; i < 20; ++i) {  
   1028         mn[v][i] = mn[pr][i];
   1029     }
   1030     for (int i = 0; i < 20; ++i) {
   1031         if ((a[v] >> i) & 1) {
   1032             if (mn[v][i] != INF) {
   1033                 W[v] = min(W[v], o);
   1034             }
   1035             mn[v][i] = min(mn[v][i], o);
   1036             mx = max(mx, s[i]);
   1037             s[i] = o;
   1038         }
   1039     }
   1040     an += o &mdash; mx;
   1041     ans[v] = an;
   1042     for (auto to: g[v]) {
   1043         if (to != pr && !us[to]) {
   1044             dfs(to, v, s, an, o + 1, mx);
   1045         }
   1046     }
   1047 }
   1048 
   1049 vector<vector<pair<int, int>>> que;
   1050 vector<int> ANS;
   1051 
   1052 void rec(int v) {
   1053     T.clear();
   1054     cnt1 = 0;
   1055     dfs1(v, -1);
   1056     dfs(v, -1);
   1057     v = h;
   1058     us[v] = true;
   1059     mn[v] = vector<int>(20, INF);
   1060     int S = E;
   1061     W[v] = INF;
   1062     for (auto to: g[v]) {
   1063         if (!us[to]) {
   1064             E++;
   1065             vector<int> s(20, 0);
   1066             dfs(to, v, s, 0, 1, 0);
   1067         }
   1068     }
   1069     ans[v] = 0;
   1070     ++E;
   1071     col[v] = E;
   1072     for (auto x: T) {
   1073         for (auto [y, id]: que[x]) {
   1074             if (col[x] != col[y] && col[x] > S && col[y] > S) {
   1075                 ANS[id] = ans[x] + ans[y];
   1076                 if (x == v) {
   1077                     int MN = min(W[y], sz[y] + 1);
   1078                     for (int i = 0; i < 20; ++i) {
   1079                         if ((a[v] >> i) & 1) {
   1080                             MN = min(MN, mn[y][i]);
   1081                         }
   1082                     }
   1083                     ANS[id] += MN;
   1084                 } else if (y == v) {
   1085                     int MN = min(W[x], sz[x] + 1);
   1086                     for (int i = 0; i < 20; ++i) {
   1087                         if ((a[v] >> i) & 1) {
   1088                             MN = min(MN, mn[x][i]);
   1089                         }
   1090                     }
   1091                     ANS[id] += MN;
   1092                 } else {
   1093                     vector<pair<int, int>> upd;
   1094                     for (int i = 0; i < 20; ++i) {
   1095                         if (mn[x][i] != INF) {
   1096                             upd.push_back({mn[x][i], i});
   1097                         }
   1098                     }
   1099                     int e = min(W[y], sz[y] + 1);
   1100                     for (int i = 0; i < 20; ++i) {
   1101                         if ((a[v] >> i) & 1) {
   1102                             e = min(e, mn[y][i]);
   1103                         }
   1104                     }
   1105                     sort(upd.begin(), upd.end());
   1106                     int p = 0;
   1107                     bool flag = true;
   1108                     for (int i = 0; i < upd.size(); ++i) {
   1109                         if (upd[i].first >= W[x]) {
   1110                             ANS[id] += (W[x] &mdash; p) * e;
   1111                             flag = false;
   1112                             break;
   1113                         }
   1114                         ANS[id] += (upd[i].first &mdash; p) * e;
   1115                         if ((a[v] >> upd[i].second) & 1) {
   1116                             flag = false;
   1117                             break;
   1118                         }
   1119                         e = min(e, mn[y][upd[i].second]);
   1120                         p = upd[i].first;
   1121                     }
   1122                     if (flag) {
   1123                         ANS[id] += (min(W[x], sz[x] + 1) &mdash; p) * e;
   1124                     }
   1125                 }
   1126             }
   1127         }
   1128     }
   1129     for (int i = 0; i < g[v].size(); ++i) {
   1130         int to = g[v][i];
   1131         if (!us[to]) {
   1132             rec(to);
   1133         }
   1134     }
   1135 }
   1136 
   1137 void solve() {
   1138     int n, q;
   1139     cin >> n >> q;
   1140     sz.clear();
   1141     W.clear();
   1142     W.resize(n);
   1143     sz.resize(n);
   1144     ans.clear();
   1145     ANS.clear();
   1146     ANS.resize(q, -1);
   1147     mn.clear();
   1148     ans.resize(n);
   1149     mn.resize(n, vector<int>(20));
   1150     a.clear();
   1151     us.clear();
   1152     us.resize(n);
   1153     a.resize(n);
   1154     for (int i = 0; i < n; ++i) {
   1155         cin >> a[i];
   1156     }
   1157     g.clear();
   1158     col.clear();
   1159     col.resize(n);
   1160     que.clear();
   1161     que.resize(n);
   1162     g.resize(n);
   1163     for (int i = 0; i < n &mdash; 1; ++i) {
   1164         int u, v;
   1165         cin >> u >> v;
   1166         --u;
   1167         --v;
   1168         g[u].push_back(v);
   1169         g[v].push_back(u);
   1170     }
   1171     for (int i = 0; i < q; ++i) {
   1172         int x, y;
   1173         cin >> x >> y;
   1174         --x;
   1175         --y;
   1176         que[x].push_back({y, i});
   1177     }
   1178     rec(0);
   1179     for (int i = 0; i < q; ++i) {
   1180         if (ANS[i] == -1) {
   1181             exit(-1);
   1182         }
   1183         cout << ANS[i] << "\n";
   1184     }
   1185 }
   1186 ```