1000.md (16932B)
1 Source: https://codeforces.com/blog/entry/60288 2 3 [1000A - Codehorses T-shirts](/contest/1000/problem/A "Educational Codeforces Round 46 (Rated for Div. 2)") 4 5 **Editorial** 6 7 Tutorial is loading... 8 9 **Solution** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 #define forn(i, n) for (int i = 0; i < int(n); i++) 15 16 using namespace std; 17 18 int main() { 19 int n; 20 cin >> n; 21 22 vector<string> a(n), b(n); 23 forn(i, n) cin >> a[i]; 24 forn(i, n) cin >> b[i]; 25 26 map<string, int> cnta, cntb; 27 forn(i, n) ++cnta[a[i]]; 28 forn(i, n) ++cntb[b[i]]; 29 30 int ans = n; 31 for (auto it : cnta) ans -= min(it.second, cntb[it.first]); 32 33 cout << ans << endl; 34 return 0; 35 } 36 ``` 37 38 [1000B - Light It Up](/contest/1000/problem/B "Educational Codeforces Round 46 (Rated for Div. 2)") 39 40 **Editorial** 41 42 Tutorial is loading... 43 44 **Solution** 45 46 ``` 47 #include<bits/stdc++.h> 48 49 using namespace std; 50 51 int n, M; 52 vector<int> a; 53 54 inline bool read() { 55 if(!(cin >> n >> M)) 56 return false; 57 a.assign(n, 0); 58 for(int i = 0; i < n; i++) 59 scanf("%d", &a[i]); 60 return true; 61 } 62 63 vector<int> f[2]; 64 65 inline void solve() { 66 a.insert(a.begin(), 0); 67 a.push_back(M); 68 69 f[0].assign(a.size(), 0); 70 f[1].assign(a.size(), 0); 71 72 for(int i = int(a.size()) - 2; i >= 0; i--) { 73 f[0][i] = f[1][i + 1]; 74 f[1][i] = (a[i + 1] - a[i]) + f[0][i + 1]; 75 } 76 77 int ans = f[1][0]; 78 for(int i = 0; i + 1 < int(a.size()); i++) { 79 if(a[i + 1] - a[i] < 2) 80 continue; 81 82 int tp = (i & 1) ^ 1; 83 int pSum = f[1][0] - f[tp][i]; 84 ans = max(ans, pSum + (a[i + 1] - a[i] - 1) + f[tp][i + 1]); 85 } 86 cout << ans << endl; 87 } 88 89 int main() { 90 #ifdef _DEBUG 91 freopen("input.txt", "r", stdin); 92 #endif 93 if(read()) 94 solve(); 95 return 0; 96 } 97 ``` 98 99 [1000C - Covered Points Count](/contest/1000/problem/C "Educational Codeforces Round 46 (Rated for Div. 2)") 100 101 **Editorial** 102 103 Tutorial is loading... 104 105 **Solution** 106 107 ``` 108 #include <bits/stdc++.h> 109 110 using namespace std; 111 112 int main() { 113 #ifdef _DEBUG 114 freopen("input.txt", "r", stdin); 115 // freopen("output.txt", "w", stdout); 116 #endif 117 118 int n; 119 scanf("%d", &n); 120 vector<pair<long long, long long>> a(n); 121 vector<long long> cval; 122 for (auto &i : a) { 123 scanf("%lld %lld", &i.first, &i.second); 124 cval.push_back(i.first); 125 cval.push_back(i.second + 1); 126 127 } 128 sort(cval.begin(), cval.end()); 129 cval.resize(unique(cval.begin(), cval.end()) - cval.begin()); 130 131 vector<int> cnt(2 * n); 132 for (auto &i : a) { 133 int posl = lower_bound(cval.begin(), cval.end(), i.first) - cval.begin(); 134 int posr = lower_bound(cval.begin(), cval.end(), i.second + 1) - cval.begin(); 135 ++cnt[posl]; 136 --cnt[posr]; 137 } 138 for (int i = 1; i < 2 * n; ++i) 139 cnt[i] += cnt[i - 1]; 140 141 vector<long long> ans(n + 1); 142 for (int i = 1; i < 2 * n; ++i) 143 ans[cnt[i - 1]] += cval[i] - cval[i - 1]; 144 145 for (int i = 1; i <= n; ++i) 146 printf("%lld ", ans[i]); 147 puts(""); 148 149 return 0; 150 } 151 ``` 152 153 [1000D - Yet Another Problem On a Subsequence](/contest/1000/problem/D "Educational Codeforces Round 46 (Rated for Div. 2)") 154 155 **Editorial** 156 157 Tutorial is loading... 158 159 **Solution** 160 161 ``` 162 #include <bits/stdc++.h> 163 164 using namespace std; 165 166 const int N = 1009; 167 const int MOD = 998244353; 168 169 int n; 170 int a[N]; 171 int dp[N]; 172 int C[N][N]; 173 174 int main() { 175 for(int i = 0; i < N; ++i){ 176 C[i][0] = C[i][i] = 1; 177 for(int j = 1; j < i; ++j) 178 C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD; 179 } 180 181 cin >> n; 182 for(int i = 0; i < n; ++i) 183 cin >> a[i]; 184 185 dp[n] = 1; 186 for(int i = n - 1; i >= 0; --i){ 187 if(a[i] <= 0) continue; 188 189 for(int j = i + a[i] + 1; j <= n; ++j){ 190 dp[i] += (dp[j] * 1LL * C[j - i - 1][a[i]]) % MOD; 191 dp[i] %= MOD; 192 } 193 } 194 195 int sum = 0; 196 for(int i = 0; i < n; ++i){ 197 sum += dp[i]; 198 sum %= MOD; 199 } 200 cout << sum << endl; 201 202 return 0; 203 } 204 ``` 205 206 [1000E - We Need More Bosses](/contest/1000/problem/E "Educational Codeforces Round 46 (Rated for Div. 2)") 207 208 **Editorial** 209 210 Tutorial is loading... 211 212 **Solution** 213 214 ``` 215 #include<bits/stdc++.h> 216 217 using namespace std; 218 219 const int N = 500043; 220 221 vector<int> g[N]; 222 vector<int> t[N]; 223 int tin[N], tout[N], fup[N]; 224 int p[N]; 225 int T = 1; 226 int rnk[N]; 227 vector<pair<int, int> > bridges; 228 int st; 229 int d[N]; 230 int n, m; 231 232 int get(int x) 233 { 234 return (p[x] == x ? x : p[x] = get(p[x])); 235 } 236 237 void link(int x, int y) 238 { 239 x = get(x); 240 y = get(y); 241 if(x == y) return; 242 if(rnk[x] > rnk[y]) 243 swap(x, y); 244 p[x] = y; 245 rnk[y] += rnk[x]; 246 } 247 248 int dfs(int x, int par = -1) 249 { 250 tin[x] = T++; 251 fup[x] = tin[x]; 252 for(auto y : g[x]) 253 { 254 if(tin[y] > 0) 255 { 256 if(par != y) 257 fup[x] = min(fup[x], tin[y]); 258 } 259 else 260 { 261 int f = dfs(y, x); 262 fup[x] = min(fup[x], f); 263 if(f > tin[x]) 264 bridges.push_back(make_pair(x, y)); 265 else 266 link(x, y); 267 } 268 } 269 tout[x] = T++; 270 return fup[x]; 271 } 272 273 void build() 274 { 275 for(auto z : bridges) 276 { 277 int x = get(z.first); 278 int y = get(z.second); 279 st = x; 280 t[x].push_back(y); 281 t[y].push_back(x); 282 } 283 } 284 285 pair<int, int> bfs(int x) 286 { 287 for(int i = 0; i < n; i++) 288 d[i] = n + 1; 289 d[x] = 0; 290 queue<int> q; 291 q.push(x); 292 int last = 0; 293 while(!q.empty()) 294 { 295 last = q.front(); 296 q.pop(); 297 for(auto y : t[last]) 298 if(d[y] > d[last] + 1) 299 { 300 d[y] = d[last] + 1; 301 q.push(y); 302 } 303 } 304 return make_pair(last, d[last]); 305 } 306 307 int main() 308 { 309 scanf("%d %d", &n, &m); 310 for(int i = 0; i < n; i++) 311 rnk[i] = 1, p[i] = i; 312 for(int i = 0; i < m; i++) 313 { 314 int x, y; 315 scanf("%d %d", &x, &y); 316 --x; 317 --y; 318 g[x].push_back(y); 319 g[y].push_back(x); 320 } 321 dfs(0); 322 build(); 323 pair<int, int> p1 = bfs(st); 324 pair<int, int> p2 = bfs(p1.first); 325 printf("%d\n", p2.second); 326 } 327 ``` 328 329 [1000F - One Occurrence](/contest/1000/problem/F "Educational Codeforces Round 46 (Rated for Div. 2)") 330 331 **Editorial** 332 333 Tutorial is loading... 334 335 **Solution with persistent segment tree** 336 337 ``` 338 #include<bits/stdc++.h> 339 340 using namespace std; 341 342 const int INF = int(1e9); 343 const int N = 500001; 344 345 typedef pair<int, int> pt; 346 347 #define x first 348 #define y second 349 #define mp make_pair 350 351 struct node 352 { 353 pt val; 354 node* l; 355 node* r; 356 node() : val(mp(INF, 0)), l(NULL), r(NULL) {}; 357 node(node* l, node* r) 358 { 359 this->val = min(l->val, r->val); 360 this->l = l; 361 this->r = r; 362 } 363 node(int pos, int val) 364 { 365 this->val = mp(val, pos); 366 this->l = NULL; 367 this->r = NULL; 368 } 369 }; 370 371 typedef node* stree; 372 373 pt query(stree t, int l, int r, int L, int R) 374 { 375 if(L >= R) 376 return mp(INF, 0); 377 if(l == L && r == R) 378 return t->val; 379 int mid = (l + r) >> 1; 380 pt q1 = query(t->l, l, mid, L, min(mid, R)); 381 pt q2 = query(t->r, mid, r, max(mid, L), R); 382 return min(q1, q2); 383 } 384 385 stree update(stree t, int l, int r, int pos, int val) 386 { 387 if(l == r - 1) 388 return new node(pos, val); 389 else 390 { 391 int mid = (l + r) >> 1; 392 if(pos < mid) 393 return new node(update(t->l, l, mid, pos, val), t->r); 394 else 395 return new node(t->l, update(t->r, mid, r, pos, val)); 396 } 397 } 398 399 stree build(int l, int r) 400 { 401 if(l == r - 1) 402 return new node(l, INF); 403 else 404 { 405 int mid = (l + r) >> 1; 406 return new node(build(l, mid), build(mid, r)); 407 } 408 } 409 410 int main() 411 { 412 int n; 413 scanf("%d", &n); 414 vector<int> a(n); 415 for(int i = 0; i < n; i++) 416 scanf("%d", &a[i]); 417 418 vector<int> left(n); 419 map<int, int> last; 420 for(int i = 0; i < n; i++) 421 { 422 if(!last.count(a[i])) 423 left[i] = -1; 424 else 425 left[i] = last[a[i]]; 426 last[a[i]] = i; 427 } 428 429 vector<stree> T(n + 1); 430 T[0] = build(0, n); 431 for(int i = 0; i < n; i++) 432 { 433 stree cur = T[i]; 434 if(left[i] != -1) 435 cur = update(cur, 0, n, left[i], INF); 436 cur = update(cur, 0, n, i, left[i]); 437 T[i + 1] = cur; 438 } 439 440 int q; 441 scanf("%d", &q); 442 for(int i = 0; i < q; i++) 443 { 444 int l, r; 445 scanf("%d %d", &l, &r); 446 --l; 447 pt ans = query(T[r], 0, n, l, r); 448 if(ans.x < l) 449 printf("%d\n", a[ans.y]); 450 else 451 printf("0\n"); 452 } 453 } 454 ``` 455 456 **Solution with persistent segment tree (a bit unreadable but runs faster)** 457 458 ``` 459 #include<bits/stdc++.h> 460 461 using namespace std; 462 463 const int INF = int(1e9); 464 const int N = 500001; 465 466 typedef pair<int, int> pt; 467 468 #define x first 469 #define y second 470 #define mp make_pair 471 472 const int M = 60 * N; 473 474 pt bufp[M]; 475 int lf[M]; 476 int rg[M]; 477 int szt = 0; 478 479 int newnode(pt val) 480 { 481 bufp[szt] = val; 482 return szt++; 483 } 484 485 int newnode(int l, int r) 486 { 487 lf[szt] = l; 488 rg[szt] = r; 489 if(bufp[l].x < bufp[r].x) 490 bufp[szt] = bufp[l]; 491 else 492 bufp[szt] = bufp[r]; 493 return szt++; 494 } 495 496 pt curans; 497 498 void query(int t, int l, int r, int L, int R) 499 { 500 if(L >= R) 501 return; 502 if(l == L && r == R) 503 { 504 if(bufp[t].x < curans.x) 505 curans = bufp[t]; 506 return; 507 } 508 int mid = (l + r) >> 1; 509 query(lf[t], l, mid, L, min(mid, R)); 510 query(rg[t], mid, r, max(mid, L), R); 511 } 512 513 int update(int t, int l, int r, int pos, int val) 514 { 515 if(l == r - 1) 516 return newnode(mp(val, pos)); 517 else 518 { 519 int mid = (l + r) >> 1; 520 if(pos < mid) 521 return newnode(update(lf[t], l, mid, pos, val), rg[t]); 522 else 523 return newnode(lf[t], update(rg[t], mid, r, pos, val)); 524 } 525 } 526 527 int build(int l, int r) 528 { 529 if(l == r - 1) 530 return newnode(mp(INF, l)); 531 else 532 { 533 int mid = (l + r) >> 1; 534 return newnode(build(l, mid), build(mid, r)); 535 } 536 } 537 538 int last[N]; 539 540 int main() 541 { 542 int n; 543 scanf("%d", &n); 544 vector<int> a(n); 545 for(int i = 0; i < n; i++) 546 scanf("%d", &a[i]); 547 548 vector<int> left(n); 549 for(int i = 0; i < N; i++) 550 last[i] = -1; 551 for(int i = 0; i < n; i++) 552 { 553 left[i] = last[a[i]]; 554 last[a[i]] = i; 555 } 556 557 vector<int> T(n + 1); 558 T[0] = build(0, n); 559 for(int i = 0; i < n; i++) 560 { 561 int cur = T[i]; 562 if(left[i] != -1) 563 cur = update(cur, 0, n, left[i], INF); 564 cur = update(cur, 0, n, i, left[i]); 565 T[i + 1] = cur; 566 } 567 568 int q; 569 scanf("%d", &q); 570 for(int i = 0; i < q; i++) 571 { 572 int l, r; 573 scanf("%d %d", &l, &r); 574 --l; 575 curans = mp(INF, 0); 576 query(T[r], 0, n, l, r); 577 if(curans.x < l) 578 printf("%d\n", a[curans.y]); 579 else 580 printf("0\n"); 581 } 582 } 583 ``` 584 585 **Solution with standard segment tree** 586 587 ``` 588 #include <bits/stdc++.h> 589 590 using namespace std; 591 592 #define forn(i, n) for(int i = 0; i < int(n); i++) 593 #define x first 594 #define y second 595 596 const int N = 500 * 1000 + 13; 597 const int INF = 1e9; 598 599 pair<pair<int, int>, int> t[4 * N]; 600 601 void build(int v, int l, int r){ 602 if (l == r - 1){ 603 t[v] = make_pair(make_pair(INF, INF), l); 604 return; 605 } 606 607 int m = (l + r) / 2; 608 609 build(v * 2, l, m); 610 build(v * 2 + 1, m, r); 611 612 t[v] = min(t[v * 2], t[v * 2 + 1]); 613 } 614 615 void update(int v, int l, int r, int pos, int prv, int nxt){ 616 if (l == r - 1){ 617 t[v].x = make_pair(nxt, prv); 618 return; 619 } 620 621 int m = (l + r) / 2; 622 623 if (pos < m) 624 update(v * 2, l, m, pos, prv, nxt); 625 else 626 update(v * 2 + 1, m, r, pos, prv, nxt); 627 628 t[v] = min(t[v * 2], t[v * 2 + 1]); 629 } 630 631 pair<pair<int, int>, int> get(int v, int l, int r, int L, int R){ 632 if (L >= R) 633 return make_pair(make_pair(INF, INF), -1); 634 635 if (l == L && r == R) 636 return t[v]; 637 638 int m = (l + r) / 2; 639 640 return min(get(v * 2, l, m, L, min(m, R)), get(v * 2 + 1, m, r, max(m, L), R)); 641 } 642 643 int n, m; 644 int a[N]; 645 pair<pair<int, int>, int> q[N]; 646 int pos[N]; 647 int ans[N]; 648 649 bool comp(const pair<pair<int, int>, int> &a, const pair<pair<int, int>, int> &b){ 650 return a.x.y < b.x.y; 651 } 652 653 int main() { 654 memset(pos, -1, sizeof(pos)); 655 scanf("%d", &n); 656 forn(i, n) scanf("%d", &a[i]); 657 scanf("%d", &m); 658 forn(i, m){ 659 scanf("%d%d", &q[i].x.x, &q[i].x.y); 660 --q[i].x.x, --q[i].x.y; 661 q[i].y = i; 662 } 663 sort(q, q + m, comp); 664 665 build(1, 0, n); 666 int lst = -1; 667 forn(i, m){ 668 int l = q[i].x.x; 669 int r = q[i].x.y; 670 671 for (int j = lst + 1; j <= r; ++j){ 672 if (pos[a[j]] != -1) 673 update(1, 0, n, pos[a[j]], -INF, j); 674 update(1, 0, n, j, pos[a[j]], -INF); 675 pos[a[j]] = j; 676 } 677 678 auto it = get(1, 0, n, l, r + 1); 679 680 if (it.y == -1 || it.x.x != -INF || it.x.y >= l){ 681 ans[q[i].y] = 0; 682 } 683 else{ 684 ans[q[i].y] = a[it.y]; 685 } 686 687 lst = r; 688 } 689 690 forn(i, m) 691 printf("%d\n", ans[i]); 692 693 return 0; 694 } 695 ``` 696 697 **Mo-based solution** 698 699 ``` 700 #include <bits/stdc++.h> 701 702 using namespace std; 703 704 #define forn(i, n) for(int i = 0; i < int(n); i++) 705 #define x first 706 #define y second 707 708 const int N = 500 * 1000 + 13; 709 const int P = 800; 710 const int INF = 1e9; 711 712 bool comp(const pair<pair<int, int>, int> &a, const pair<pair<int, int>, int> &b){ 713 int num = a.x.x / P; 714 if (num != b.x.x / P) 715 return a.x.x < b.x.x; 716 if (num & 1) 717 return a.x.y < b.x.y; 718 return a.x.y > b.x.y; 719 } 720 721 int val[N]; 722 int cnt[N]; 723 int bl[P]; 724 int tot; 725 726 inline void add(int x){ 727 ++cnt[x]; 728 if (cnt[x] == 1){ 729 ++val[x]; 730 ++bl[x / P]; 731 ++tot; 732 } 733 else if (cnt[x] == 2){ 734 --val[x]; 735 --bl[x / P]; 736 --tot; 737 } 738 } 739 740 inline void sub(int x){ 741 --cnt[x]; 742 if (cnt[x] == 1){ 743 ++val[x]; 744 ++bl[x / P]; 745 ++tot; 746 } 747 else if (cnt[x] == 0){ 748 --val[x]; 749 --bl[x / P]; 750 --tot; 751 } 752 } 753 754 int get(){ 755 if (tot == 0) 756 return 0; 757 758 forn(i, P){ 759 if (bl[i] > 0){ 760 for (int j = i * P;; ++j){ 761 if (val[j]){ 762 return j; 763 } 764 } 765 } 766 } 767 768 assert(false); 769 } 770 771 int n, m; 772 int a[N], ans[N]; 773 pair<pair<int, int>, int> q[N]; 774 775 int main() { 776 scanf("%d", &n); 777 forn(i, n) scanf("%d", &a[i]); 778 scanf("%d", &m); 779 forn(i, m){ 780 scanf("%d%d", &q[i].x.x, &q[i].x.y); 781 --q[i].x.x, --q[i].x.y; 782 q[i].y = i; 783 } 784 sort(q, q + m, comp); 785 786 int l = 0, r = -1; 787 788 forn(i, m){ 789 int L = q[i].x.x; 790 int R = q[i].x.y; 791 792 while (r < R){ 793 ++r; 794 add(a[r]); 795 } 796 797 while (r > R){ 798 sub(a[r]); 799 --r; 800 } 801 802 while (l > L){ 803 --l; 804 add(a[l]); 805 } 806 807 while (l < L){ 808 sub(a[l]); 809 ++l; 810 } 811 812 ans[q[i].y] = get(); 813 } 814 815 forn(i, m) 816 printf("%d\n", ans[i]); 817 818 return 0; 819 } 820 ``` 821 822 [1000G - Two-Paths](/contest/1000/problem/G "Educational Codeforces Round 46 (Rated for Div. 2)") 823 824 **Editorial** 825 826 Tutorial is loading... 827 828 **Solution** 829 830 ``` 831 #include<bits/stdc++.h> 832 833 using namespace std; 834 835 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 836 837 #define sz(a) int((a).size()) 838 #define all(a) (a).begin(), (a).end() 839 840 #define x first 841 #define y second 842 843 typedef long long li; 844 typedef long double ld; 845 typedef pair<int, int> pt; 846 847 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 848 return out << "(" << p.x << ", " << p.y << ")"; 849 } 850 851 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 852 out << "["; 853 fore(i, 0, sz(v)) { 854 if(i) out << ", "; 855 out << v[i]; 856 } 857 return out << "]"; 858 } 859 860 const int M = 400 * 1000 + 555; 861 const int N = 300 * 1000 + 555; 862 const int LOGN = 19; 863 864 int n, m, a[N]; 865 vector<pt> g[N]; 866 867 inline bool read() { 868 if(!(cin >> n >> m)) 869 return false; 870 fore(i, 0, n) 871 assert(scanf("%d", &a[i]) == 1); 872 fore(i, 0, n - 1) { 873 int u, v, w; 874 assert(scanf("%d%d%d", &u, &v, &w) == 3); 875 u--, v--; 876 877 g[u].emplace_back(v, w); 878 g[v].emplace_back(u, w); 879 } 880 fore(i, 0, n) 881 sort(all(g[i])); 882 return true; 883 } 884 885 int tin[N], tout[N], T = 0; 886 int p[N][LOGN]; 887 888 int h[N]; 889 li d1[N]; 890 891 void calc1(int v, int pr) { 892 tin[v] = T++; 893 p[v][0] = pr; 894 fore(st, 1, LOGN) 895 p[v][st] = p[p[v][st - 1]][st - 1]; 896 897 d1[v] = a[v]; 898 fore(i, 0, sz(g[v])) { 899 int to = g[v][i].x; 900 int w = g[v][i].y; 901 902 if(to == pr) 903 continue; 904 905 h[to] = h[v] + 1; 906 calc1(to, v); 907 d1[v] += max(0ll, d1[to] - 2ll * w); 908 } 909 tout[v] = T++; 910 } 911 912 li dp[N]; 913 vector<li> dto[N]; 914 915 void calcRRT(int v) { 916 dp[v] = a[v]; 917 dto[v].assign(sz(g[v]), 0ll); 918 919 fore(i, 0, sz(g[v])) { 920 int to = g[v][i].x; 921 int w = g[v][i].y; 922 923 li curVal = max(0ll, d1[to] - 2ll * w); 924 dp[v] += curVal; 925 dto[v][i] = curVal; 926 } 927 928 fore(i, 0, sz(g[v])) { 929 int to = g[v][i].x; 930 if(h[to] < h[v]) 931 continue; 932 933 li tmp = d1[v]; 934 d1[v] = dp[v] - dto[v][i]; 935 calcRRT(to); 936 d1[v] = tmp; 937 } 938 } 939 940 inline bool isP(int l, int v) { 941 return tin[l] <= tin[v] && tout[v] <= tout[l]; 942 } 943 944 int lca(int u, int v) { 945 if(isP(u, v)) return u; 946 if(isP(v, u)) return v; 947 948 for(int st = LOGN - 1; st >= 0; st--) 949 if(!isP(p[v][st], u)) 950 v = p[v][st]; 951 return p[v][0]; 952 } 953 954 li getDto(int v, int to) { 955 int pos = int(lower_bound(all(g[v]), pt(to, -1)) - g[v].begin()); 956 if(pos >= sz(g[v]) || g[v][pos].x != to) 957 return 0; 958 return dto[v][pos]; 959 } 960 961 li f[N]; 962 963 inline void inc(int pos, li val) { 964 for(; pos < N; pos |= pos + 1) 965 f[pos] += val; 966 } 967 968 inline li sum(int pos) { 969 li ans = 0; 970 for(; pos >= 0; pos = (pos & (pos + 1)) - 1) 971 ans += f[pos]; 972 return ans; 973 } 974 975 inline li getSum(int l, int r) { 976 return sum(r) - sum(l); 977 } 978 979 li ans[M]; 980 vector<pt> qs[N]; 981 982 void calcAns(int v) { 983 li vAdd = dp[v] - getDto(v, p[v][0]); 984 inc(h[v], vAdd); 985 986 for(pt &q : qs[v]) { 987 int up = q.x, id = q.y; 988 ans[id] += getSum(h[up] - 1, h[v]) + getDto(up, p[up][0]); 989 } 990 991 fore(i, 0, sz(g[v])) { 992 int to = g[v][i].x; 993 int w = g[v][i].y; 994 if(h[to] < h[v]) 995 continue; 996 997 li curSub = dto[v][i] + w; 998 inc(h[v], -curSub); 999 1000 calcAns(to); 1001 inc(h[v], +curSub); 1002 } 1003 inc(h[v], -vAdd); 1004 } 1005 1006 inline void solve() { 1007 T = 0; 1008 h[0] = 0; 1009 calc1(0, 0); 1010 calcRRT(0); 1011 1012 fore(i, 0, m) { 1013 int u, v; 1014 assert(scanf("%d%d", &u, &v) == 2); 1015 u--, v--; 1016 1017 int l = lca(u, v); 1018 ans[i] = -dp[l]; 1019 1020 qs[u].emplace_back(l, i); 1021 qs[v].emplace_back(l, i); 1022 } 1023 1024 calcAns(0); 1025 fore(i, 0, m) 1026 printf("%lld\n", ans[i]); 1027 } 1028 1029 int main() { 1030 #ifdef _DEBUG 1031 freopen("input.txt", "r", stdin); 1032 int tt = clock(); 1033 #endif 1034 cout << fixed << setprecision(15); 1035 1036 if(read()) { 1037 solve(); 1038 1039 #ifdef _DEBUG 1040 cerr << "TIME = " << clock() - tt << endl; 1041 tt = clock(); 1042 #endif 1043 } 1044 return 0; 1045 } 1046 ```