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 — 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 — 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] — p) * e; 1111 flag = false; 1112 break; 1113 } 1114 ANS[id] += (upd[i].first — 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) — 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 — 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 ```