4 条题解
-
4
题目大意
题目描述清楚，不做赘述
解题思路
区修点查，考虑线段树
第一步，把节点按dfs序编号，节点 记为 ，将树拆开
第二步，建线段树
观察修改操作
显然地，将 到 这一段加 即可，线段树区修
子树中每个节点 增加值不相等，为 。由于单点查询， 可以在查询时进行计算，所以将 与 分别存入线段树，区修
#include<bits/stdc++.h> using namespace std; #define int long long #define N 100010 int n,m; vector<int>G[N]; int a[N]; int tsp,dfn[N],_dfn[N],siz[N]; int dis[N]; int dep[N]; void dfs(int x,int xfa){//拆树 dfn[x]=++tsp;_dfn[tsp]=x;siz[x]=1; dis[x]=dis[xfa]+a[x]; dep[x]=dep[xfa]+1; for(int y:G[x])if(y!=xfa){ dfs(y,x); siz[x]+=siz[y]; } } #define lc(p) (p<<1) #define rc(p) (p<<1|1) #define MID ((l+r)>>1) struct node{ int l,r,sum1,sum2;//分别为 dep[y] 的系数与常数 int tag1,tag2; }tr[N<<2]; void pushdown(int p){ if(tr[p].tag1){ tr[lc(p)].tag1+=tr[p].tag1;tr[lc(p)].sum1+=tr[p].tag1; tr[rc(p)].tag1+=tr[p].tag1;tr[rc(p)].sum1+=tr[p].tag1; tr[p].tag1=0; } if(tr[p].tag2){ tr[lc(p)].tag2+=tr[p].tag2;tr[lc(p)].sum2+=tr[p].tag2; tr[rc(p)].tag2+=tr[p].tag2;tr[rc(p)].sum2+=tr[p].tag2; tr[p].tag2=0; } } void build(int p,int l,int r){ if(l==r){ tr[p]={l,r,dis[_dfn[l]],0,0,0}; return; } tr[p]={l,r,0,0,0,0}; build(lc(p),l,MID);build(rc(p),MID+1,r); } void chg(int p,int l,int r,int x,int y){ if(tr[p].r<l||tr[p].l>r)return; if(l<=tr[p].l&&tr[p].r<=r){ tr[p].sum1+=x; tr[p].tag1+=x; tr[p].sum2+=y; tr[p].tag2+=y; return; } pushdown(p); chg(lc(p),l,r,x,y);chg(rc(p),l,r,x,y); } int query(int p,int pos){ if(tr[p].r<pos||tr[p].l>pos)return -1e15; if(tr[p].l==tr[p].r){ return tr[p].sum1+tr[p].sum2*dep[_dfn[tr[p].l]]; } pushdown(p); return max(query(lc(p),pos),query(rc(p),pos)); } signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<n;i++){ int x,y;cin>>x>>y; G[x].push_back(y);G[y].push_back(x); } dep[0]=dis[0]=0; dfs(1,0); build(1,1,n); for(int i=1;i<=m;i++){ int op,x,y;cin>>op>>x; if(op==1){ cin>>y; chg(1,dfn[x],dfn[x]+siz[x]-1,y,0); } else if(op==2){ cin>>y; chg(1,dfn[x],dfn[x]+siz[x]-1,-(dep[x]-1)*y,y); } else{ cout<<query(1,dfn[x])<<'\n'; } } return 0; } -
1
taojinghua LV 9 @ 2026-8-25 15:00:44
GG
#include<bits/stdc++.h> using namespace std; #define ll long long const ll N=1e5+10; ll n,m,a[N],dep[N],fa[N],son[N],siz[N],top[N],dfn[N],_dfn[N],tsp; vector<ll>G[100010]; void dfs(ll x,ll xfa) { dep[x]=dep[xfa]+1;fa[x]=xfa;siz[x]=1;son[x]=-1; for(ll y:G[x])if(y!=xfa) { dfs(y,x); siz[x]+=siz[y]; if(son[x]<0||siz[son[x]]<siz[y])son[x]=y; } } void dfs2(ll x,ll tp) { top[x]=tp;dfn[x]=++tsp;_dfn[tsp]=x; if(son[x]!=-1)dfs2(son[x],tp); for(ll y:G[x])if(y!=fa[x]&&y!=son[x])dfs2(y,y); } #define lc(p) (p<<1) #define rc(p) (p<<1|1) struct node{ll tag,l,r,s;}tr[N<<2]; void pushup(ll p){tr[p].s=tr[lc(p)].s+tr[rc(p)].s;} void pushdown(ll p) { if(tr[p].tag) { ll t=tr[p].tag; tr[lc(p)].tag+=t;tr[rc(p)].tag+=t; tr[lc(p)].s+=t*(tr[lc(p)].r-tr[lc(p)].l+1); tr[rc(p)].s+=t*(tr[rc(p)].r-tr[rc(p)].l+1); tr[p].tag=0; } } void build(ll p,ll l,ll r) { tr[p]={0,l,r,0}; if(l==r){tr[p].s=a[_dfn[l]];return;} ll mid=(l+r)/2; build(lc(p),l,mid);build(rc(p),mid+1,r); pushup(p); } void change(ll p,ll x,ll k) { if(tr[p].r<x||x<tr[p].l)return; if(tr[p].l==tr[p].r){tr[p].s+=k;return;} pushdown(p); change(lc(p),x,k);change(rc(p),x,k); pushup(p); } void change2(ll p,ll l,ll r,ll k) { if(tr[p].r<l||r<tr[p].l)return; if(l<=tr[p].l&&tr[p].r<=r) { tr[p].s+=k*(tr[p].r-tr[p].l+1); tr[p].tag+=k; return; } pushdown(p); change2(lc(p),l,r,k);change2(rc(p),l,r,k); pushup(p); } ll q(ll p,ll l,ll r) { if(tr[p].r<l||r<tr[p].l)return 0; if(l<=tr[p].l&&tr[p].r<=r)return tr[p].s; pushdown(p); return q(lc(p),l,r)+q(rc(p),l,r); } ll q2(ll x) { ll ans=0; while(top[x]!=1) { ans+=q(1,dfn[top[x]],dfn[x]); x=fa[top[x]]; } ans+=q(1,dfn[1],dfn[x]); return ans; } int main() { scanf("%lld%lld",&n,&m); for(ll i=1;i<=n;i++)scanf("%lld",&a[i]); for(ll i=1,x,y;i<n;i++) { scanf("%lld%lld",&x,&y); G[x].push_back(y);G[y].push_back(x); } dfs(1,0);dfs2(1,1); build(1,1,n); for(ll i=1,op,x,y;i<=m;i++) { scanf("%lld%lld",&op,&x); if(op==1)scanf("%lld",&y),change(1,dfn[x],y); else if(op==2)scanf("%lld",&y),change2(1,dfn[x],dfn[x]+siz[x]-1,y); else printf("%lld\n",q2(x)); } return 0; }-
第一组数据(巨长)......
输入：
1000 1000 127413 -950783 -114985 -549241 936991 968553 261627 653907 884965 -594937 504085 40913 -895669 849313 993633 502831 98260 616831 20928 594976 146469 -268450 -421945 109705 776948 481159 27279 -546401 782513 698621 458543 712431 -771103 429083 -722900 661387 -439680 966017 -838851 186469 413297 31001 69501 665081 -904705 -81148 147301 -656001 764147 480415 -657925 -43181 867434 833986 -686063 959707 -444956 943886 -849229 842071 74157 974109 -978986 487876 793025 631825 195201 212415 343518 899152 -487479 756253 -919718 585570 396812 613185 272766 937651 228604 288394 -447980 384479 292489 112158 224753 -786997 223366 424167 407 343779 306364 40658 557517 -877625 -716406 156333 584876 -428039 811632 -770642 391651 17866 72801 -815854 -71153 -623241 342781 432313 785203 470864 421551 433676 546891 295545 41866 -381153 418351 958391 202104 382263 -261185 150965 -794232 -602574 25049 -874201 -753617 860984 263675 -351281 29713 -60801 -158777 433531 873017 -313670 357848 29244 282787 -153909 527971 -181511 762449 763505 -376908 106683 -160468 506401 63953 -12524 633421 -74592 23437 -769111 559081 488601 436769 22401 941591 -575780 937771 -234001 355548 623254 11717 266755 926557 816277 -17723 -590377 406892 87765 350937 495457 -678816 -432497 786817 433751 644033 -840036 262151 37969 957929 693534 937441 60609 -362829 -33001 -692591 -967804 815253 -246876 216587 -505143 89393 415527 -754177 407589 409210 -127441 175153 920647 531957 211669 451097 886737 413825 -924975 643668 949859 393657 806206 -321161 33348 -314715 -213389 696371 687723 537246 118595 966681 386321 203737 349812 488803 875201 -38601 -412610 628722 758672 -756861 589792 536257 465084 697986 922033 596447 147429 556223 -254003 611705 109177 -152946 -985809 260601 -23605 316745 92796 803238 -492207 930961 617617 -723909 656869 -110092 655169 946697 780443 108039 -916541 502337 660401 -101155 931753 -518761 249721 429483 555221 444289 777459 -499591 811767 -353855 197511 864624 213911 567317 606241 657287 265679 301425 177768 918285 -716171 252801 -887545 325491 192021 310945 -663679 -997689 969465 436209 314411 48568 74701 426693 592051 64597 832763 611901 373761 803209 4715 237289 -317439 -78751 -127825 -668685 -747937 904968 -811761 638349 103774 898786 450679 -229481 -408346 535591 -806069 -846813 -661109 871889 178975 688439 960337 125132 -482785 995881 516031 870715 13500 148421 920441 293777 -567273 -659701 137207 328227 98453 897974 -801195 528501 702196 321024 854429 318401 930857 328299 644980 498949 244629 104573 357459 836773 -106081 278541 -854241 609845 725213 815736 646873 89601 -350457 631360 549345 502401 485757 12513 -121257 217907 -234877 -215873 -129561 -416103 500587 281503 220067 677605 168451 812751 -720780 625413 38514 585668 317565 -954959 -673516 928730 -354781 710721 325792 296673 198544 424681 -986218 -533539 404733 534376 -804863 823831 40739 963531 222001 117449 -259761 671391 486805 182299 473769 636028 477790 351907 485374 324957 457185 -175694 144165 386301 199773 -162345 824711 179654 164929 -726478 145815 -701151 298161 -949523 300941 343517 718433 41706 -824791 868341 471911 191107 647996 965106 -341425 38861 572165 833093 -267946 565709 973527 949631 344902 724233 188939 712050 814860 582865 170429 -171181 705827 204183 -578689 -400466 177509 944974 -789126 690485 843097 -726917 42331 563721 401296 648953 31057 -661591 176963 -967889 -724761 785982 237987 917111 -943407 494781 -40051 468269 375549 -294865 226051 -558133 315305 203945 184054 18661 675648 145301 681506 142781 -254505 -261088 102763 401102 960393 446509 704581 124009 903123 -966733 558701 665273 869425 582811 20801 802241 70751 293139 99001 267264 279191 698254 268500 586393 25315 217529 950246 554498 474785 25596 722071 782901 631071 322353 628614 -501631 614991 -634581 35401 -327648 827081 945997 561160 641251 408324 -121561 -787768 -724998 630800 -652632 354125 190486 477635 447441 970379 917478 312327 509075 246171 71501 474741 -650451 336180 3537 902080 -845577 926680 492666 668511 953987 249738 164805 -663226 724929 440385 271994 -8534 690353 321417 602019 372257 91369 938993 883537 -148217 -700986 66121 -417604 928316 239730 907561 -855792 -734701 -868121 665574 331243 -451939 -793431 738381 945086 -949711 -254919 62916 -856436 536891 -864295 403914 753717 827519 -293045 -221661 -465861 445605 286155 272145 239905 265727 495629 755143 -331037 207106 847137 -395579 -168595 535761 129587 -832231 806725 761411 986903 -690849 528190 130201 354431 293121 366191 -175766 766333 573391 441419 345465 165195 377327 -674901 893705 7621 901673 962052 470441 -289846 470011 -732963 187761 821341 577491 418605 -670604 801305 426001 58333 526401 983609 197470 -222210 -37067 297367 378034 55631 312961 -443859 -89075 -504860 130649 -502032 235457 -729385 -157861 909761 -345225 628409 -723161 869614 640997 465875 625429 296039 -582785 261321 351169 -28454 285647 35707 460851 327413 48123 806218 841623 774921 501841 324642 653601 659459 256641 619009 617517 558736 -914851 -64337 464449 -587626 -397565 -517727 -206382 339298 169233 12951 272255 875189 541571 782535 698467 -587505 104581 -913739 902421 -434372 -685877 -326582 -486355 804209 660865 13973 557496 649573 927861 -290050 64879 -740197 175385 -862010 -313335 -512926 279601 724511 961393 144042 710941 458257 53003 633396 956423 985949 -48236 641281 189676 -732276 -188391 894031 -971763 436655 686586 233712 659076 222982 947435 42809 -893635 341481 666715 -328081 41246 -183931 931781 627291 639345 421551 -929213 759742 340651 273537 358237 454988 956409 36351 929201 973937 11619 965673 456677 51429 917239 739226 -338711 342706 352170 722359 627791 420354 -218709 107137 -166984 -376571 -895441 607875 305233 989721 346890 -545043 870636 507301 879029 835596 -615149 595685 -494610 3716 -905906 -105601 463673 146877 845945 308664 -214721 254151 73806 133801 935761 469295 693261 -781967 390001 -695651 903043 -504441 -652545 -622541 224562 928447 635601 165021 89062 -809322 144885 566981 -464721 50781 -835602 -513333 738115 -3651 650881 -141254 -97381 282641 756353 -486727 646567 -865173 337611 58161 956881 569581 529313 464967 171721 -728589 -208672 608888 -963469 533761 681718 601069 -656993 -649829 563099 995210 544173 832194 400911 -890946 257201 129447 -844033 -949727 -894831 -448535 348189 81371 81458 687620 712763 -26489 750181 465557 751261 -238494 -26039 909390 24009 271913 990352 -454168 653441 610609 -409825 963581 9619 668736 960004 407283 -45649 839877 881057 464649 288061 669759 871898 -774931 -534775 -176169 80613 230866 787761 -672681 -334443 -523835 670177 445264 686065 -358465 49461 99182 -427830 557793 3749 149861 778296 352897 523899 900481 224557 -266241 560728 -536901 413005 524246 741801 184433 443557 84401 552151 690587 860166 -876969 991427 14845 368576 -223473 546273 941544 653299 657383 223133 658567 609141 965441 405521 220877 685254 525091 983945 217937 97451 317041 367301 105998 815725 540564 130783 446901 -68734 784905 161811 728321 703181 11393 543061 629195 -455353 175998 503125 641533 212561 646079 639579 946653 828585 79339 -892587 725541 198457 733001 453383 302741 54189 396755 630209 2 1 3 1 4 1 5 3 6 3 7 5 8 2 9 5 10 1 11 1 12 6 13 7 14 11 15 1 16 13 17 1 18 5 19 13 20 1 21 9 22 7 23 18 24 5 25 21 26 10 27 13 28 26 29 1 30 6 31 25 32 24 33 21 34 27 35 27 36 8 37 35 38 10 39 23 40 15 41 37 42 40 43 13 44 2 45 29 46 1 47 1 48 36 49 40 50 15 51 23 52 34 53 3 54 48 55 33 56 39 57 51 58 42 59 20 60 50 61 41 62 26 63 13 64 22 65 26 66 20 67 60 68 24 69 55 70 42 71 18 72 30 73 55 74 47 75 51 76 4 77 9 78 61 79 2 80 2 81 41 82 13 83 32 84 32 85 73 86 73 87 23 88 73 89 77 90 21 91 1 92 43 93 67 94 22 95 18 96 82 97 41 98 22 99 1 100 56 101 45 102 70 103 13 104 17 105 46 106 87 107 64 108 73 109 15 110 109 111 67 112 30 113 109 114 49 115 1 116 37 117 43 118 19 119 84 120 107 121 100 122 89 123 50 124 13 125 63 126 6 127 121 128 14 129 41 130 57 131 11 132 55 133 17 134 68 135 69 136 84 137 69 138 10 139 89 140 110 141 3 142 14 143 95 144 6 145 49 146 76 147 89 148 10 149 145 150 86 151 67 152 61 153 1 154 143 155 113 156 113 157 69 158 141 159 21 160 12 161 57 162 66 163 87 164 13 165 113 166 95 167 129 168 124 169 148 170 165 171 39 172 87 173 151 174 154 175 157 176 3 177 129 178 145 179 88 180 32 181 151 182 61 183 73 184 85 185 58 186 61 187 139 188 98 189 177 190 184 191 141 192 54 193 69 194 158 195 167 196 90 197 61 198 171 199 89 200 147 201 161 202 73 203 5 204 36 205 43 206 181 207 23 208 82 209 157 210 110 211 170 212 188 213 41 214 13 215 33 216 33 217 205 218 175 219 6 220 163 221 171 222 11 223 193 224 162 225 92 226 77 227 163 228 19 229 196 230 98 231 29 232 45 233 88 234 206 235 146 236 76 237 229 238 1 239 230 240 179 241 83 242 200 243 183 244 66 245 5 246 156 247 100 248 210 249 153 250 215 251 106 252 66 253 123 254 163 255 116 256 190 257 97 258 145 259 55 260 95 261 85 262 136 263 214 264 223 265 22 266 219 267 255 268 235 269 186 270 247 271 59 272 199 273 10 274 103 275 187 276 2 277 103 278 3 279 37 280 218 281 21 282 257 283 43 284 238 285 222 286 134 287 189 288 106 289 49 290 17 291 185 292 239 293 285 294 45 295 199 296 251 297 207 298 283 299 77 300 107 301 79 302 62 303 161 304 172 305 210 306 246 307 277 308 171 309 33 310 244 311 103 312 75 313 305 314 167 315 173 316 298 317 313 318 283 319 192 320 218 321 257 322 268 323 151 324 287 325 253 326 289 327 2 328 268 329 83 330 281 331 37 332 99 333 235 334 253 335 217 336 68 337 97 338 254 339 289 340 100 341 157 342 331 343 323 344 322 345 141 346 231 347 51 348 24 349 327 350 219 351 229 352 274 353 43 354 259 355 31 356 291 357 343 358 1 359 239 360 145 361 331 362 227 363 274 364 264 365 225 366 349 367 24 368 179 369 185 370 366 371 118 372 108 373 285 374 173 375 331 376 67 377 200 378 299 379 153 380 242 381 353 382 127 383 315 384 376 385 305 386 110 387 330 388 166 389 59 390 128 391 65 392 84 393 157 394 310 395 103 396 316 397 221 398 26 399 14 400 310 401 205 402 130 403 231 404 399 405 341 406 281 407 391 408 353 409 97 410 359 411 116 412 181 413 394 414 117 415 153 416 207 417 299 418 282 419 397 420 281 421 166 422 182 423 43 424 55 425 73 426 422 427 135 428 52 429 1 430 175 431 23 432 126 433 379 434 307 435 327 436 238 437 145 438 77 439 70 440 405 441 394 442 280 443 48 444 144 445 253 446 156 447 339 448 332 449 15 450 57 451 1 452 382 453 258 454 439 455 263 456 81 457 220 458 164 459 425 460 43 461 212 462 301 463 331 464 187 465 241 466 267 467 174 468 460 469 97 470 14 471 121 472 442 473 237 474 417 475 131 476 341 477 122 478 406 479 461 480 181 481 7 482 92 483 40 484 422 485 159 486 11 487 109 488 47 489 393 490 308 491 134 492 204 493 457 494 244 495 229 496 166 497 437 498 215 499 295 500 374 501 372 502 214 503 3 504 275 505 49 506 61 507 273 508 66 509 388 510 443 511 181 512 127 513 39 514 248 515 1 516 324 517 175 518 309 519 512 520 362 521 49 522 384 523 175 524 171 525 485 526 232 527 143 528 264 529 67 530 396 531 317 532 376 533 71 534 200 535 92 536 261 537 341 538 148 539 103 540 253 541 293 542 263 543 440 544 263 545 486 546 276 547 197 548 499 549 181 550 334 551 75 552 416 553 523 554 462 555 165 556 461 557 409 558 339 559 528 560 161 561 441 562 264 563 469 564 53 565 90 566 546 567 361 568 46 569 517 570 256 571 455 572 20 573 86 574 79 575 511 576 295 577 129 578 568 579 347 580 245 581 312 582 502 583 460 584 32 585 425 586 402 587 493 588 239 589 141 590 539 591 275 592 293 593 416 594 218 595 568 596 449 597 465 598 379 599 116 600 174 601 181 602 362 603 213 604 588 605 210 606 602 607 427 608 558 609 371 610 218 611 113 612 469 613 493 614 550 615 351 616 301 617 463 618 437 619 207 620 390 621 15 622 508 623 31 624 342 625 394 626 319 627 285 628 610 629 205 630 185 631 543 632 376 633 340 634 343 635 601 636 290 637 509 638 450 639 564 640 249 641 240 642 153 643 399 644 198 645 625 646 103 647 247 648 187 649 327 650 143 651 443 652 604 653 485 654 33 655 220 656 274 657 580 658 145 659 325 660 339 661 97 662 589 663 479 664 354 665 521 666 371 667 361 668 418 669 331 670 373 671 621 672 348 673 169 674 554 675 35 676 550 677 79 678 519 679 535 680 180 681 296 682 501 683 69 684 368 685 619 686 174 687 308 688 49 689 515 690 561 691 417 692 375 693 125 694 344 695 309 696 463 697 58 698 471 699 135 700 197 701 117 702 697 703 154 704 478 705 419 706 662 707 568 708 70 709 331 710 236 711 35 712 573 713 273 714 314 715 267 716 133 717 249 718 90 719 294 720 269 721 135 722 674 723 677 724 600 725 93 726 549 727 393 728 305 729 197 730 160 731 395 732 353 733 409 734 81 735 290 736 366 737 417 738 167 739 235 740 494 741 186 742 397 743 189 744 403 745 404 746 171 747 309 748 181 749 377 750 215 751 163 752 507 753 97 754 427 755 185 756 655 757 445 758 149 759 459 760 321 761 481 762 21 763 343 764 373 765 361 766 238 767 495 768 8 769 106 770 230 771 272 772 56 773 384 774 403 775 316 776 526 777 111 778 634 779 151 780 478 781 681 782 713 783 589 784 769 785 637 786 461 787 299 788 193 789 627 790 293 791 321 792 768 793 301 794 237 795 97 796 486 797 293 798 769 799 356 800 750 801 269 802 543 803 385 804 131 805 125 806 350 807 393 808 652 809 66 810 62 811 145 812 299 813 81 814 784 815 33 816 9 817 31 818 178 819 33 820 780 821 249 822 427 823 674 824 269 825 369 826 31 827 87 828 11 829 499 830 682 831 333 832 597 833 80 834 542 835 599 836 211 837 419 838 721 839 603 840 814 841 1 842 642 843 735 844 166 845 453 846 476 847 325 848 192 849 134 850 53 851 732 852 334 853 649 854 309 855 31 856 681 857 229 858 604 859 850 860 379 861 273 862 653 863 573 864 450 865 627 866 860 867 398 868 30 869 544 870 334 871 303 872 139 873 37 874 561 875 315 876 786 877 79 878 610 879 501 880 842 881 21 882 203 883 451 884 103 885 86 886 542 887 286 888 693 889 424 890 321 891 81 892 663 893 685 894 409 895 351 896 228 897 363 898 432 899 19 900 453 901 602 902 35 903 481 904 1 905 331 906 316 907 52 908 142 909 894 910 136 911 361 912 71 913 837 914 33 915 555 916 676 917 313 918 322 919 283 920 376 921 321 922 421 923 811 924 251 925 868 926 293 927 199 928 450 929 685 930 735 931 349 932 694 933 409 934 4 935 695 936 133 937 761 938 102 939 623 940 711 941 179 942 569 943 808 944 798 945 413 946 291 947 122 948 652 949 68 950 109 951 680 952 199 953 946 954 582 955 471 956 866 957 643 958 731 959 57 960 247 961 251 962 467 963 315 964 195 965 596 966 299 967 37 968 116 969 216 970 758 971 611 972 825 973 453 974 324 975 653 976 391 977 882 978 117 979 646 980 929 981 645 982 937 983 23 984 254 985 517 986 661 987 273 988 901 989 731 990 447 991 514 992 139 993 845 994 785 995 356 996 941 997 549 998 595 999 456 1000 190 1 665 700505 3 313 3 381 1 622 936331 1 681 795851 3 865 3 230 1 899 -750215 3 244 2 511 512371 2 945 -234263 3 321 1 341 432236 1 169 -575631 3 936 1 655 745319 3 866 1 556 527027 1 721 203187 1 618 130045 3 561 1 257 -540016 2 437 478836 2 451 378545 2 297 414085 2 371 993779 2 558 176946 1 947 251793 1 941 759475 3 258 1 968 -819445 1 353 586765 1 849 122026 2 141 869945 1 595 -554081 3 55 2 585 968269 1 766 350125 2 801 971773 3 855 3 101 3 208 1 374 481477 1 636 -295876 3 291 1 337 370913 3 153 2 65 -33371 1 553 -539056 1 752 -743385 3 569 2 737 102552 1 193 197905 2 373 -174593 1 681 573235 2 176 902625 2 577 706876 1 569 957001 3 329 1 511 908793 1 593 -985799 3 514 1 451 -128751 1 419 282856 1 454 559097 3 91 3 745 1 325 714427 1 21 86811 1 182 855039 1 333 641045 1 679 947311 3 941 1 104 789985 1 209 463801 1 931 -519835 3 441 1 281 241609 1 509 83767 3 429 3 1 1 781 79001 1 547 269021 1 187 -622078 2 411 170577 1 465 641981 3 646 3 729 2 389 532728 1 326 582783 3 405 1 301 -337672 1 291 -656436 1 951 -706989 1 146 113225 1 611 981545 1 809 966081 2 733 242993 3 745 1 756 517825 3 639 1 373 999477 1 261 561775 1 819 80706 1 590 522188 1 831 499040 1 951 674105 2 373 97409 1 141 78401 1 989 593499 2 726 367893 1 7 491905 3 471 1 193 443601 1 671 401141 1 846 416376 1 339 -989948 2 277 -687503 2 530 866513 1 937 943977 2 835 213901 3 453 1 990 -734501 2 423 -535912 3 953 1 751 167869 1 264 714938 2 217 58297 1 109 -33241 1 162 133356 3 143 1 81 341685 1 167 185731 3 826 3 962 1 598 793107 3 601 1 249 361815 1 769 24156 3 421 1 521 -177675 1 45 442025 2 899 -226791 3 461 2 8 377469 1 817 951553 1 457 923472 1 701 918514 2 371 726209 3 410 2 713 875017 1 633 28273 1 257 699191 1 577 259937 1 81 995377 1 425 432557 1 645 300001 1 217 835871 1 817 -422241 1 649 -213857 1 375 96121 3 91 2 625 -442873 2 841 102533 2 771 179469 3 166 1 457 257761 1 713 65795 1 101 726444 1 765 348473 2 701 -836421 1 765 -66384 1 721 41985 1 85 200261 3 467 2 981 -576391 3 850 1 658 -716845 1 645 -821919 3 908 1 906 825673 2 885 -612919 1 961 -776891 3 617 1 329 -464046 1 386 639371 1 808 164529 1 36 768973 1 601 995461 1 31 -451609 3 261 1 103 666603 1 77 424086 1 300 873976 1 121 330223 1 417 888193 1 502 358637 1 54 -894039 2 413 -737422 1 581 275136 1 346 708935 2 399 198828 1 802 789730 1 545 850226 1 345 -435361 1 395 -338033 3 811 1 34 -63327 3 281 3 371 1 861 887381 1 56 442084 1 470 292595 1 813 18777 1 624 357921 3 769 3 617 1 991 778753 1 841 503325 1 897 17547 2 971 268041 1 401 938812 1 137 382073 2 309 -95495 3 858 3 379 1 141 558887 1 651 488111 2 411 307075 1 904 453447 1 305 -458909 1 951 994516 3 177 1 1 655331 1 637 214583 2 179 -354482 2 46 476200 1 116 833517 1 621 68865 1 537 634065 2 999 251252 1 243 -85091 1 687 -965112 2 376 -837681 3 47 2 764 473837 1 705 684489 1 922 -376235 3 661 1 799 67305 1 776 245201 1 447 212273 1 301 346881 1 561 473147 1 360 317981 1 28 936836 1 223 -55240 1 194 -311135 1 679 115741 2 796 101633 2 161 -906154 2 162 137604 1 106 204689 1 905 -842635 1 900 -634497 1 769 908025 1 15 875073 2 249 832751 1 221 492651 1 911 -794773 1 828 527918 1 827 186593 3 281 1 202 186313 3 105 1 917 219713 2 881 363837 1 689 296384 3 135 1 729 -793640 3 10 3 318 3 62 1 838 -289509 1 81 829729 1 701 240381 2 100 936978 1 969 -610858 1 541 -725323 3 69 1 491 639391 3 322 2 697 823681 3 876 3 327 2 8 978440 2 567 -385604 3 942 1 251 -673789 1 1 -636625 1 395 114397 2 465 97875 3 351 1 145 485566 1 369 763431 1 401 -288865 2 3 -397697 1 91 371071 1 15 21491 1 301 854980 2 328 44261 1 59 -270225 1 75 34226 1 569 912689 1 188 -85063 1 351 807809 1 251 236558 1 776 4385 1 649 861419 1 900 405925 1 871 378600 1 549 617736 3 1 2 281 765089 1 394 -10689 1 681 676713 1 313 597595 3 92 1 213 508269 3 665 1 270 -844365 1 754 201677 1 953 957153 1 903 375905 1 549 787893 2 715 107357 3 897 2 435 877586 2 836 883991 2 509 -264569 3 869 1 501 -768491 1 660 883230 1 817 951987 3 601 1 813 156778 1 16 122261 1 183 976836 1 156 60776 1 81 408873 1 821 479033 1 869 443873 3 469 1 893 764481 1 887 601770 1 842 663609 1 311 88211 3 45 2 969 665581 1 360 766081 2 401 878918 1 521 225506 1 517 338881 1 193 -274696 1 401 -983589 1 694 445589 1 70 652541 1 283 51307 2 65 -423001 2 265 56529 1 347 -897471 1 821 935507 2 411 402326 1 50 334698 3 451 2 522 562391 1 430 609599 1 563 863041 3 216 3 449 3 281 1 686 467778 3 631 1 283 683377 1 887 182728 1 703 421985 1 973 -937785 3 725 1 962 443065 2 431 234511 1 841 922238 1 26 462599 3 998 1 53 946761 3 745 3 24 1 73 71853 1 499 789769 3 67 2 929 -208695 3 797 3 25 1 608 761412 2 733 128016 1 161 -413346 1 905 612614 1 841 -687141 1 169 -449209 2 571 -667281 1 271 748821 1 678 875106 2 557 198147 2 761 -395705 2 716 44651 1 945 267839 1 786 241731 1 74 -395831 3 953 2 477 -244986 1 190 961251 2 705 369153 3 787 2 214 631941 2 361 845601 1 564 -33723 1 526 259251 1 307 -820529 2 838 427571 2 490 361929 1 353 -324042 3 504 3 94 3 409 3 751 3 535 1 25 606882 2 51 129457 3 437 3 591 3 713 2 177 28238 2 286 280665 1 224 286761 1 774 -170394 1 15 584561 1 161 859335 2 101 201299 1 914 185775 2 433 -617403 1 81 -838045 3 384 3 696 1 747 -455881 1 511 885945 1 705 206547 1 961 -357591 1 329 -614916 1 197 -815787 3 788 3 985 1 621 -376239 3 524 1 801 709749 1 599 -375719 1 43 -238069 1 649 405803 3 281 2 975 23366 1 1 577512 1 351 975891 1 447 -236415 1 752 -138125 3 553 1 245 689633 2 145 -172975 1 969 942105 1 65 151357 2 469 36841 2 425 50733 2 1 170105 1 327 -184451 2 1 596815 1 776 586649 2 211 305708 3 393 1 747 647527 3 300 1 738 299181 2 816 631077 3 189 1 417 808133 3 639 2 372 823511 1 153 -546998 1 201 595537 3 581 1 46 497946 3 119 1 412 816838 3 671 2 27 634991 1 985 614365 1 88 244427 3 73 3 257 2 721 -893025 2 505 586011 1 978 498993 2 721 -307876 1 1 -74973 2 486 -301599 1 312 65641 1 173 297397 1 157 181263 1 852 -479931 2 185 -39484 1 765 792361 3 236 1 751 720850 2 605 612215 3 153 1 672 -792681 2 821 -896433 3 248 1 73 201789 3 731 1 289 609998 1 23 -244965 1 297 -443243 3 414 1 381 723671 2 625 645773 3 165 1 401 599889 1 205 -921307 1 72 988061 1 249 163271 3 887 2 837 334433 1 189 68281 1 159 459353 1 761 811855 1 490 244753 2 459 138435 1 321 -401536 1 747 -627201 2 751 20001 2 729 -606138 1 235 965629 1 666 621251 1 969 -307159 1 108 500245 1 639 -493345 2 825 863675 1 613 590417 1 535 155067 1 846 433611 1 823 866081 3 45 1 101 784733 1 193 689741 2 173 7915 1 485 327591 2 801 506453 2 313 775241 3 381 1 769 406957 1 879 264721 1 631 848641 1 125 -779863 1 84 135089 1 561 298901 3 451 2 807 521223 2 733 51986 1 489 56593 2 5 463689 1 609 -680768 2 18 774831 3 887 1 957 694541 2 605 542853 2 1 554777 1 661 -222891 1 362 691019 1 801 468481 2 21 589081 3 223 1 925 123505 1 592 41681 1 381 766947 1 21 476 1 1 476221 3 472 1 937 -849719 2 422 397159 1 175 737724 3 913 3 643 1 121 -869852 1 20 416469 2 547 611075 1 533 577473 1 990 797618 2 45 408357 1 896 590867 2 969 126833 1 148 651521 2 825 740289 1 4 525702 3 241 1 796 394207 1 607 -430910 1 289 243809 1 98 115428 1 531 499062 1 691 272541 2 544 97057 1 497 721893 1 674 303751 3 881 1 687 514209 2 1 622977 1 15 -3251 2 961 614687 1 491 424011 3 513 1 969 -28353 2 11 74321 3 186 1 292 -57104 1 817 384090 1 558 -796810 3 235 1 501 130415 1 890 206951 2 319 -543544 1 176 497001 1 300 745891 1 445 220748 1 484 -361849 2 206 171081 1 45 253610 3 201 3 645 2 362 -379718 2 285 720166 3 301 1 473 376159 1 577 998751 1 417 251369 1 183 705001 2 471 460193 2 75 804181 2 868 -27661 1 921 106407 1 293 323616 1 737 96481 3 837 3 266 1 878 -409775 1 225 338261 2 417 866177 1 297 815321 3 256 1 857 557089 1 561 899441 1 745 518651 2 101 709601 1 221 103950 3 193 1 579 529705 1 365 660871 2 393 310673 3 375 1 298 -842040 1 421 656744 1 261 915013 1 905 840511 1 469 571225 1 14 779744 1 549 583653 1 340 -125566 2 460 -70495 3 189 1 765 124031 1 256 -309992 2 522 236940 3 474 1 519 -421797 1 121 -785001 1 1 44828 1 275 651681 1 126 368001 1 265 436539 1 577 399860 3 806 3 61 1 333 135485 1 446 636581 1 495 383776 1 497 -395135 2 516 -554905 1 501 -264238 1 341 570092 3 722 2 607 181068 1 722 758981 1 547 25878 2 335 -12537 1 996 264331 1 852 164025 3 449 1 856 -981501 2 493 660151 1 402 394715 1 895 579787 1 67 321309 2 833 976155 1 609 858177 2 701 -952290 3 701 2 799 136145 2 491 458075 1 181 402873 3 386 1 893 767420 2 345 557281 2 789 567289 1 801 486796 2 513 157914 1 226 -975824 1 229 -736281 3 129 1 698 -399669 2 565 186782 2 771 900931 3 380 3 889 2 320 -873663 1 817 -66741 1 456 614881 3 329 1 325 779029 2 896 719341 1 461 104272 1 649 673279 1 112 -763281 2 855 281901 1 345 416456 3 317 1 178 856667 1 841 154133 3 665 1 571 972501 3 111 1 931 670689 1 923 678273 2 836 -729944 1 381 814601 2 193 22281 2 343 89157 3 412 2 967 -845377 2 445 -891177 2 211 757649 2 811 -817831 1 990 -303715 3 393 3 1 3 881 3 911 1 831 400447 2 852 808173 3 201 1 825 -918561 2 839 -962552 1 201 -970946 1 409 -929125 1 241 -277721 2 429 472117 3 537 2 997 919548 1 621 63751 3 805 1 721 -619317 2 137 214305 1 1 127041 2 31 603609 2 101 -733553 2 37 352541 1 805 -323335 3 299 1 541 3311 2 54 957126 1 87 51133 2 373 775186 3 990 1 237 571489 3 859 1 219 -121441 1 771 624966 1 385 655205 1 970 417423 2 138 98441 1 521 130473 2 441 126401 1 701 413111 3 973 3 413 1 381 91761 3 461 2 994 53681 1 401 361901 1 865 182951 3 361 1 172 544276 2 834 62137 3 26 1 776 224816 1 854 -647599 2 781 831534 1 126 351761 1 425 -929881 1 737 -369558 1 194 726861 1 839 768193 2 507 -176253 3 201 2 751 648497 2 603 434891 1 503 208634 1 151 450691 2 231 -9696 2 553 823993 1 301 803649 1 565 111466 1 268 445929 3 51 1 617 275742 1 963 55881 1 897 -399243 1 879 284810 1 226 516761 1 331 449969 1 93 953045 1 221 974065 1 101 508837 1 181 -454965 1 516 444067 3 865 1 180 545702 1 621 618916 1 157 24458 1 857 -343236 1 746 -608921 1 409 438581 1 401 44291 2 594 -971921 1 635 233713 3 827 3 383 1 350 651264 1 67 659789 2 995 226229 3 301 3 977 3 433 2 611 357921 1 19 138959 3 611 1 855 368961 1 442 -857281 1 511 -527801 3 591 1 752 -849346 1 580 209481 2 113 306029 2 211 -707931 1 593 66198 2 815 466041 1 826 219841 1 337 324023 2 193 581971 1 836 604498 3 27 3 739 1 113 744221 1 506 -728417 2 136 219067 1 539 406130 2 951 580653 2 300 137641 1 852 931751 3 861 1 531 324221 1 512 96716 1 838 187881 1 656 35129 3 252 2 407 769521 1 257 303201 2 117 872588 3 81 1 151 490945 3 81 1 125 798896 1 913 -947616 3 51 2 198 509906 1 608 727342 2 902 92558 1 713 876689 1 396 -485177 1 9 -30882 1 697 681041 1 77 -951173 2 601 134101 2 966 969959 1 623 195651 1 185 751683 1 693 711050 3 70 1 894 320855 3 69 3 581 3 1 3 803 1 650 -128329 3 759 3 285 1 827 945569 3 885 3 943 1 137 -99117 1 409 345481 1 257 913425 2 761 512573 2 441 214535 3 257 1 851 997407 2 801 450727 3 221 1 223 612941 1 851 928913 1 161 445057 3 204 1 137 2654 1 548 690303 2 306 -220441 1 441 684097 1 20 3484 1 633 -720300 3 805 2 137 299864 1 199 -187461 1 197 984289 3 585 1 521 -402593 2 226 370793 1 129 999761 1 408 -162338 1 221 225881 1 791 471281 1 860 767135 1 751 -963345 1 853 599793 2 703 123829 1 241 463661 1 919 -265585 1 661 510151 1 785 -680501 1 25 -443476 2 778 -428353 1 787 288815 3 712 1 307 726186 1 465 40965 3 189 2 881 540833 1 641 343404 3 361 1 601 83781 1 79 749921 1 81 -243138 1 233 -1573 1 931 57917 3 601 1 595 48268 1 178 -670836 2 129 851593 3 761 1 233 23601 1 573 513471 1 677 943992 1 417 984153 3 271 1 371 474433 1 116 830199 1 793 161113输出：
4202610 1302202 2226120 1273229 368405 278133 627624 -37210 350539 2475197 523687 3785925 396872 -225119 2222154 150850 1483545 3059925 3698959 433777 3223137 1702888 -142127 -822110 127413 575939 -1376697 2838444 3223137 1137221 -428257 3058062 3367428 1612293 4206198 2587614 4288022 954254 2724641 3404971 433777 1116599 1902360 1526429 1587361 1064586 1179906 1589153 2610698 3724496 1190137 1064586 2936991 828455 1135770 930045 1381116 3266029 1582843 2482364 187807 2042053 1643075 1609347 1658694 2197228 -42907 3626245 3973347 146119 -1450035 3559400 -700916 -1074060 6198753 -2639157 465952 1107963 -1284304 2760549 1406008 -2540635 4460191 1655345 3838327 -115261 3888701 2333410 874833 5239851 571063 -307719 -1412903 -3105811 19946 -901735 3765533 -1659851 920674 3337001 -2468442 -1670984 -2077185 -1330756 1406008 -3508439 6373603 7919596 5924246 4890289 4797939 5664293 8076322 3710332 10641340 4702315 1658937 9990417 4880260 5415165 8268586 6501636 3269251 6415158 3144342 9283770 19778591 28382479 27215541 9728948 12857357 12485429 17969524 26615101 13321418 23869194 16458759 9657486 31747504 10897996 31040487 23736814 23972114 29608650 21928540 12269911 23953663 16260860 10199469 16960853 15544346 24143181 23140635 22091421 16568238 23706616 17057848 17904503 23965373 26333629 3114381 16268119 27919815 23914022 31501648 16507019 15299483 22292770 11046518 20565445 14621330 21594926 27182925 7479591 23070117 15399015 17778553 18669631 26724405 10633004 14994805 8653791 16625573 23298711 14173202 15582003 9622921 11336331 26353809 26353809 15399015 15260788 20004916 26098870 3241422 23024886 25662173 11161780 22788411 29839331 30969742 23603865 16432998 17109621 23204957 27171156 32542985 27632894 25911306 16145074 9220149
-
-
1
只能说是树链剖分板子，没啥好说的。
#include<bits/stdc++.h> #define int long long #define lc(p) (p<<1) #define rc(p) (p<<1|1) using namespace std; constexpr int N=1e5+10; vector<int>G[N]; int fa[N],son[N],dep[N],siz[N]; inline void dfs1(int x,int xfa){ fa[x]=xfa;dep[x]=dep[xfa]+1;siz[x]=1;son[x]=-1; for(int y:G[x])if(y!=xfa){ dfs1(y,x); siz[x]+=siz[y]; if(son[x]==-1||siz[son[x]]<siz[y])son[x]=y; } } int tsp,dfn[N],_dfn[N],top[N]; inline void dfs2(int x,int tp){ dfn[x]=++tsp;_dfn[tsp]=x;top[x]=tp; if(son[x]>0)dfs2(son[x],tp); for(int y:G[x])if(y!=fa[x]&&y!=son[x])dfs2(y,y); } struct trnode{ int l,r,c,tag; }tr[N<<2]; int a[N]; inline void pushup(int p){ tr[p].c=tr[lc(p)].c+tr[rc(p)].c; } inline void pushdown(int p){ if(tr[p].tag){ tr[lc(p)].c+=tr[p].tag*(tr[lc(p)].r-tr[lc(p)].l+1); tr[lc(p)].tag+=tr[p].tag; tr[rc(p)].c+=tr[p].tag*(tr[rc(p)].r-tr[rc(p)].l+1); tr[rc(p)].tag+=tr[p].tag; tr[p].tag=0; } } inline void build(int p,int l,int r){ tr[p]={l,r,0,0}; if(l==r){ tr[p].c=a[_dfn[l]]; return; } int m=l+r>>1; build(lc(p),l,m); build(rc(p),m+1,r); pushup(p); } inline void change(int p,int l,int r,int c){ if(l<=tr[p].l&&tr[p].r<=r){ tr[p].c+=c*(tr[p].r-tr[p].l+1); tr[p].tag+=c; return; } pushdown(p); int m=tr[p].l+tr[p].r>>1; if(l<=m)change(lc(p),l,r,c); if(r>m)change(rc(p),l,r,c); pushup(p); } inline int query1(int p,int l,int r){ if(l<=tr[p].l&&tr[p].r<=r)return tr[p].c; pushdown(p); int m=tr[p].l+tr[p].r>>1,res=0; if(l<=m)res+=query1(lc(p),l,r); if(r>m)res+=query1(rc(p),l,r); return res; } inline int query2(int x){ int res=0; while(top[x]!=1){ res+=query1(1,dfn[top[x]],dfn[x]); x=fa[top[x]]; } res+=query1(1,dfn[1],dfn[x]); return res; } int n,m; signed main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<n;i++){ int x,y; cin>>x>>y; G[x].emplace_back(y); G[y].emplace_back(x); } dfs1(1,0); tsp=0; dfs2(1,1); build(1,1,tsp); while(m--){ int op; cin>>op; if(op==1){ int x,val; cin>>x>>val; change(1,dfn[x],dfn[x],val); }else if(op==2){ int x,val; cin>>x>>val; change(1,dfn[x],dfn[x]+siz[x]-1,val); }else{ int x; cin>>x; cout<<query2(x)<<"\n"; } } } -
0
huangzheng
LV 6
@ 2025-10-8 17:09:43
#include<cstdio> #include<cstring> #include<algorithm> #define ri register int using namespace std; typedef long long ll; char ch[10]; int n,m,op,x,y,tot,v[200010]; ll c; struct tree{ll c,tag;}tr[800010]; int len,last[200010]; struct edge{int x,y,next;}a[400010]; int fa[200010],size[200010],dep[200010],son[200010],top[200010],id[200010]; inline void pushup(int now){tr[now].c=tr[now<<1].c+tr[now<<1|1].c;} inline void f(int now,int l,int r,ll k){tr[now].c+=(r-l+1)*k;tr[now].tag+=k;} inline void pushdown(int now,int l,int r) { if(!tr[now].tag||l==r) return; int mid=(l+r)>>1; f(now<<1,l,mid,tr[now].tag); f(now<<1|1,mid+1,r,tr[now].tag); tr[now].tag=0; } inline void update(int ul,int ur,ll k,int now,int l,int r) { if(ul<=l&&r<=ur) { tr[now].c+=(r-l+1)*k; tr[now].tag+=k; return; } pushdown(now,l,r); int mid=(l+r)>>1; if(ul<=mid) update(ul,ur,k,now<<1,l,mid); if(ur>mid) update(ul,ur,k,now<<1|1,mid+1,r); pushup(now); } inline ll query(int ql,int qr,int now,int l,int r) { if(ql<=l&&r<=qr) return tr[now].c; pushdown(now,l,r); int mid=(l+r)>>1; ll res=0; if(ql<=mid) res+=query(ql,qr,now<<1,l,mid); if(qr>mid) res+=query(ql,qr,now<<1|1,mid+1,r); return res; } inline void add(int x,int y) { len++; a[len].x=x,a[len].y=y; a[len].next=last[x],last[x]=len; } void dfs1(int x,int f) { fa[x]=f,dep[x]=dep[f]+1,size[x]=1,son[x]=0; for(ri i=last[x];i;i=a[i].next) { int y=a[i].y; if(y!=fa[x]) { dfs1(y,x); if(size[y]>size[son[x]]) son[x]=y; size[x]+=size[y]; } } } void dfs2(int x,int tp) { id[x]=++tot,top[x]=tp; if(son[x]) dfs2(son[x],tp); for(ri i=last[x];i;i=a[i].next) { int y=a[i].y; if(y!=fa[x]&&y!=son[x]) dfs2(y,y); } } ll solve(int x,int y) //注意：原代码中solve函数参数是x,y，返回从x到y的路径和，这里按原代码逻辑保留 { ll ans=0; //但根据参数和逻辑，可能实际是求x到根的路径和？需要结合题目，这里按原代码输出 int tx=top[x],ty=top[y]; while(tx!=ty) //重链分解，将路径拆分为重链段 { if(dep[tx]>dep[ty]) swap(x,y),swap(tx,ty); ans+=query(id[ty],id[y],1,1,tot); //计算当前重链段的贡献 y=fa[ty],ty=top[y]; } if(dep[x]>dep[y]) swap(x,y); //确保x是y的祖先 ans+=query(id[x],id[y],1,1,tot); //计算最后一段重链 return ans; //返回路径和 } int main() { scanf("%d %d",&n,&m); for(ri i=1;i<=n;i++) scanf("%d",&v[i]); len=0; memset(last,0,sizeof(last)); for(ri i=1;i<=n-1;i++) //读入n-1条边，建立无向图 { scanf("%d %d",&x,&y); add(x,y),add(y,x); } dep[0]=0; dfs1(1,1); //第一次DFS，计算fa,dep,size,son tot=0; dfs2(1,1); //第二次DFS，计算id,top，建立重链 for(ri i=1;i<=n;i++) update(id[i],id[i],v[i],1,1,tot); //初始化线段树，每个点的值为v[i] for(ri i=1;i<=m;i++) //m次操作 { scanf("%d",&op); if(op==1) scanf("%d %lld",&x,&c),update(id[x],id[x],c,1,1,tot); //单点更新 if(op==2) scanf("%d %lld",&x,&c),update(id[x],id[x]+size[x]-1,c,1,1,tot); //区间更新（整颗子树） if(op==3) scanf("%d",&x),printf("%lld\n",solve(x,1)); //查询x到根的路径和 } return 0; }
Yangzhichao
LV 10
@ 2026-8-25 14:45:27
- 1
