QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#684586#9373. Query on TreewyxqwqWA 3311ms79484kbC++145.8kb2024-10-28 14:32:542024-10-28 14:32:54

Judging History

你现在查看的是最新测评结果

  • [2024-10-28 14:32:54]
  • 评测
  • 测评结果:WA
  • 用时:3311ms
  • 内存:79484kb
  • [2024-10-28 14:32:54]
  • 提交

answer

#include<bits/stdc++.h>
#define vectorwyx maze
namespace vectorwyx{
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define sml(x,y) (x=min(x,y))
#define big(x,y) (x=max(x,y))
#define ll long long
#define uint unsigned
#define ull unsigned long long
#define umap unordered_map
#define db double
#define fo(i,x,y) for(int i=(x);i<=(y);++i)
#define go(i,x,y) for(int i=(x);i>=(y);--i)
#define ptc putchar
#define gtc getchar
#define emp emplace
#define re return
#define co continue
#define brk break
#define HH (ptc('\n'))
#define bctz __builtin_ctz
#define bclz __builtin_clz
#define bppc __builtin_popcount
#define int ll
using namespace std;
ll seed=chrono::system_clock::now().time_since_epoch().count();
mt19937 rnd(seed);
inline int rm(int x,int y){return (int)(rnd()%(y-x+1ll)+x);}
inline int read(){signed ch=getchar();int x=0,f=1;while(!isdigit(ch)){if(ch==(int)('-'))f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline ll llread(){signed ch=getchar();ll x=0,f=1;while(!isdigit(ch)){if(ch==(int)('-'))f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
template<typename T> void out(T *a,int l,int r){fo(i,l,r) cout<<*(a+i)<<' ';puts("");}

const int N=2e5+5,K=9;
const ll inf=1e18;
vector<int> e[N];
int bfn[N],tb,bod[N],dod[N],bL[N][K+2],bR[N][K+2],fa[N][K+2],dL[N],dR[N],td,n;
ll a[N];

void init(){
    fo(i,1,K) fa[1][i]=0;
    fo(i,1,n) e[i].clear(),fa[i][0]=i;
    fo(i,1,n) fo(j,0,K) bL[i][j]=n+1,bR[i][j]=0;
    tb=td=0;
}

void dfs1(int x){
    for(int i:e[x]) if(i!=fa[x][1]){
        fo(j,1,K) fa[i][j]=fa[x][j-1];
        dfs1(i);
    }
}

void bfs(){
    queue<int> q;q.push(1);
    while(!q.empty()){
        int x=q.front();q.pop();
        bfn[x]=++tb;bod[tb]=x;
        fo(i,0,K) if(fa[x][i]) sml(bL[fa[x][i]][i],bfn[x]),big(bR[fa[x][i]][i],bfn[x]); 
        for(int i:e[x]) if(i!=fa[x][1]) q.push(i);
    }
    // cout<<"bfn:";out(bfn,1,n);
}

void dfs2(int x){
    if(!bR[x][K]) re;
    dL[x]=++td;dod[td]=x;
    for(int i:e[x]) if(i!=fa[x][1]) dfs2(i);
    dR[x]=td;
}

namespace Tree_b{
ll b[N];
void build(){fo(i,1,n) b[i]=a[bod[i]];}
void update(int l,int r,ll v){fo(i,l,r) b[i]+=v;}
ll ask(int l,int r){
    ll ret=-inf;fo(i,l,r) big(ret,b[i]);
    // printf("Tree_b::ask(%d,%d)=%lld\n",l,r,ret);
    re ret;
}
}

namespace Tree_d{
ll tag[N],mx[N];
void build(){
    fo(i,1,n){
        tag[i]=0,mx[i]=-inf;
        if(bR[i][K]) fo(j,bL[i][K],bR[i][K]) big(mx[dL[i]],a[bod[j]]);
    }
    // cout<<"Tree_d::mx:";out(mx,1,n);
}
void update(int l,int r,ll v){
    // printf("update(%d,%d,%lld)\n",l,r,v);
    fo(i,l,r) tag[i]+=v,mx[i]+=v;
}
ll ask(int l,int r){
    ll ret=-inf;fo(i,l,r) big(ret,mx[i]);
    // printf("ask(%d,%d)=%lld\n",l,r,ret);
    re ret;
}
void clr_tag(int x){
    Tree_b::update(bL[x][K],bR[x][K],tag[dL[x]]);
    tag[dL[x]]=0;
}
void reset(int x){mx[dL[x]]=Tree_b::ask(bL[x][K],bR[x][K]);}
}

void gao(int l,int r,int v){
    // printf("gao(%d,%d,%d)\n",l,r,v);
    if(l>r) re;
    
    int x=bod[l];
    assert(fa[x][K]==fa[bod[r]][K]);
    x=fa[x][K];
    if(!x){Tree_b::update(l,r,v);re;}
    Tree_d::clr_tag(x);
    Tree_b::update(l,r,v);
    Tree_d::reset(x);
}

ll nbor(int x,int k,int v){
    // printf("nbor(%d,%d,%d)\n",x,k,v);
    if(!fa[x][1]){
        ll ret=-inf;
        fo(i,0,k){
            if(!bR[x][i]) break;
            gao(bL[x][i],bR[x][i],v);
            big(ret,Tree_b::ask(bL[x][i],bR[x][i]));
        }
        re ret;
    }
    // puts("qwq");
    gao(bL[x][k],bR[x][k],v);
    // puts("qaq");
    if(k==0) re Tree_b::ask(bfn[x],bfn[x]);
    gao(bL[x][k-1],bR[x][k-1],v);
    ll ret=max(Tree_b::ask(bL[x][k],bR[x][k]),Tree_b::ask(bL[x][k-1],bR[x][k-1]));
    re max(ret,nbor(fa[x][1],k-1,v));
}

void solve(){
    cin>>n;int q=read();init();
    fo(i,1,n) a[i]=llread();
    fo(i,2,n){
        int x=read(),y=read();
        e[x].pb(y),e[y].pb(x);
    }
    dfs1(1);
    bfs();
    td=0;dfs2(1);
    // fo(i,1,n){cout<<i<<":";fo(j,0,K) printf("[%d,%d] ",bL[i][j],bR[i][j]);HH;}
    // fo(i,1,n) printf("[%d,%d] ",dL[i],dR[i]);HH;
    Tree_b::build();Tree_d::build();
    while(q--){
        int o=read(),x=read();
        if(o==3){
            int v=read();
            ll ans=-inf;
            fo(i,0,K-1){
                if(!bR[x][i]) break;
                gao(bL[x][i],bR[x][i],v);
                big(ans,Tree_b::ask(bL[x][i],bR[x][i]));
            }
            if(bR[x][K]) Tree_d::update(dL[x],dR[x],v),big(ans,Tree_d::ask(dL[x],dR[x]));
            cout<<ans<<'\n';
            co;
        }
        int k=read(),v=read();
        if(o==1){
            ll ans=-inf;
            if(bR[x][k]) gao(bL[x][k],bR[x][k],v),big(ans,Tree_b::ask(bL[x][k],bR[x][k]));
            fo(i,1,k){
                if(!fa[x][i]) break;
                int l=bL[fa[x][i]][k-i],r=bR[fa[x][i]][k-i];
                if(!r) co;
                if(i==k){gao(l,r,v);big(ans,Tree_b::ask(l,r));break;}
                int L=bL[fa[x][i-1]][k-i-1],R=bR[fa[x][i-1]][k-i-1];
                if(!R){gao(l,r,v),big(ans,Tree_b::ask(l,r));co;}
                if(l<L) gao(l,L-1,v),big(ans,Tree_b::ask(l,L-1));
                if(r>R) gao(R+1,r,v),big(ans,Tree_b::ask(R+1,r));
            }
            if(ans==-inf) puts("GG");
            else cout<<ans<<'\n';
            co;
        }
        cout<<nbor(x,k,v)<<'\n';
    }
}

signed main(){
    int T=read();
    while(T--) solve();
    return 0;
}
}
/*
1
5 5
1 2 1 3 2
1 2
2 3
2 4
4 5
2 2 1 0
1 2 1 3
3 4 -5
2 5 2 3
3 2 -1
-------------------------------------------------

*/










signed main(){re vectorwyx::main();}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 24596kb

input:

1
5 5
1 2 1 3 2
1 2
2 3
2 4
4 5
2 2 1 0
1 2 1 3
3 4 -5
2 5 2 3
3 2 -1

output:

3
6
1
5
4

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 41ms
memory: 24972kb

input:

10000
3 9
42973045452542 34994498886390 -91733395797555
1 3
1 2
1 1 5 -71952967
3 1 -816873082
1 1 5 -842437577
2 3 7 254550528
3 3 -854082700
2 3 2 699808309
3 3 554885567
1 2 7 595565507
1 3 0 -318374053
3 2
-63158159333100 77264362049163 -99188430131116
1 2
3 2
2 2 4 -305866230
3 1 -549738403
3 5...

output:

GG
42972228579460
GG
42972483129988
-91734812202809
42973182938297
-91733557508933
GG
-91733875882986
77264056182933
77263506444530
7065382376488
7065749360235
7066534912965
-85115611272570
-85114714781312
96492412785032
-20428913156111
-20428197540063
96491742171666
-14945310996805
96491180203461
-...

result:

ok 200000 lines

Test #3:

score: 0
Accepted
time: 40ms
memory: 25732kb

input:

10000
4 32
-1057044448491 -93293078803919 -24212938548357 74427756948193
1 3
1 2
3 4
3 1 -82365883
1 2 9 -730670945
2 4 2 -618745828
2 1 2 774032949
3 3 6733210
3 3 -843683844
3 1 327410390
3 1 -865685600
1 4 6 -951367966
3 2 107763506
1 3 2 721870187
2 3 3 -530847597
2 2 1 451029291
3 2 231297873
3...

output:

74427674582310
GG
74427055836482
74427829869431
74427836602641
74426992918797
74427320329187
74426454643587
GG
-93292817648557
-93292095778370
74425923795990
-1057589620769
-93291944298803
74425228504438
74425430401539
-93291936231808
74425906008467
GG
-1058067327518
74424997886529
74424370598990
74...

result:

ok 200000 lines

Test #4:

score: 0
Accepted
time: 35ms
memory: 24908kb

input:

10000
5 21
-17119694111919 -49543801764535 15340078463236 -13731655847398 -41385234314814
3 2
1 5
1 4
1 2
3 5 865538081
3 4 551893736
2 3 9 797578233
1 3 0 -657534941
3 4 -507570975
1 1 2 352656478
3 5 951666995
2 5 3 524459610
3 4 819153725
2 4 0 955588629
3 5 -451248313
1 3 0 -251438755
1 4 0 -707...

output:

-41384368776733
-13731103953662
15340876041469
15340218506528
-13730813946404
15340571163006
-41382619531505
15341095622616
-13729470333069
-13728514744440
-41382546320208
15340844183861
-13729221899958
15340255675017
-13729490336654
-13729529150761
-13729624738248
15341124008689
15341173814500
GG
-...

result:

ok 200000 lines

Test #5:

score: 0
Accepted
time: 40ms
memory: 25684kb

input:

10000
7 53
-49257878340663 65913602617244 -77586447275975 37912663831730 -29965751459870 -24028915786606 -20711244730875
2 1
3 1
4 6
1 5
7 1
2 4
1 6 4 -614276625
3 7 -430532617
3 3 -970301980
1 1 4 767992650
2 1 4 88036223
2 3 5 -930151770
3 3 -816226996
1 2 1 -696978838
2 1 1 -877781309
2 5 2 58619...

output:

-20711859007500
-20712289540117
-77588031854580
GG
65913690653467
65912760501697
-77589690197123
37911124737345
65911882720388
65912468916628
65911745912774
-29967336843362
65911988615088
GG
37910494006281
65912545393218
-49259038263999
GG
65913255260627
GG
GG
65912963550828
-24029074909413
65912862...

result:

ok 200000 lines

Test #6:

score: 0
Accepted
time: 36ms
memory: 25560kb

input:

10000
10 4
71797802165245 -54234031880796 29183815458453 29504172959957 49372193603523 -16185389362615 39453295094243 663036651923 96744787191200 -50620611104201
5 8
5 1
1 2
4 7
7 10
2 4
5 6
3 9
3 2
3 7 -830615007
1 2 6 637860195
2 7 7 -843886558
3 8 273999944
10 8
-33479821641433 91082116968197 -34...

output:

39452464479236
GG
96743943304642
662466765309
91246631814706
-29877405744477
GG
GG
91081604757708
GG
91246614330784
-29877381879548
-4361386733251
89595437158302
-4360828297147
19337184792075
89595109336295
89594748412265
19336971357477
89594978989869
86993545918633
-84286253125550
GG
GG
52174855696...

result:

ok 200000 lines

Test #7:

score: 0
Accepted
time: 24ms
memory: 24800kb

input:

10000
3 9
42973045452542 34994498886390 -91733395797555
2 3
2 1
3 1 -988613092
1 2 0 308890489
1 1 0 472776476
2 2 2 -122992202
2 3 1 831940219
3 3 -612896282
3 3 -536438981
1 1 0 161104440
2 1 1 354965461
3 2
77441670935132 -63158159333100 77264362049163
3 1
2 1
1 3 4 -20585631
1 1 6 747193249
3 5
...

output:

42972056839450
34993819163787
42972529615926
42972406623724
34994528111804
-91734288358912
-91734824797893
42972567728164
42972922693625
GG
GG
GG
7064655135811
-61568732738930
7065157020537
-61568593058530
80122234728388
80122047274326
80122140239806
80121956639200
80121963373184
80121401404979
9259...

result:

ok 200000 lines

Test #8:

score: 0
Accepted
time: 19ms
memory: 25800kb

input:

10000
4 32
-1057044448491 -93293078803919 -24212938548357 74427756948193
3 2
4 1
1 2
1 2 8 639477246
1 4 0 510694922
2 1 0 421373363
2 3 4 -843809269
3 1 -620938865
3 3 -933234989
1 3 3 458028025
1 4 6 -951367966
3 2 107763506
1 3 2 721870187
2 3 3 -530847597
2 2 1 451029291
3 2 231297873
3 1 -69529...

output:

GG
74428267643115
-1056623075128
74427423833846
74426802894981
-24215336531480
74427260923006
GG
-24215228767974
-1057365953075
74426730075409
-1057445771381
-24215077288407
74426034783857
74426236680958
-24215069221412
74426712287886
74427585548383
74427327526258
-24215759758547
-24216387046086
744...

result:

ok 200000 lines

Test #9:

score: 0
Accepted
time: 32ms
memory: 24124kb

input:

10000
5 21
-17119694111919 -49543801764535 15340078463236 -13731655847398 -41385234314814
1 2
4 1
5 1
1 3
3 4 -183603675
1 1 6 750831651
2 4 2 -112044052
2 5 0 487266103
2 4 7 623494631
2 3 6 -758745863
2 5 3 524459610
3 4 819153725
2 4 0 955588629
3 5 -451248313
1 3 0 -251438755
1 4 0 -707155518
3 ...

output:

-13731839451073
GG
15339966419184
-41384859092763
15340589913815
15339831167952
15340355627562
-13730743133022
-13729787544393
-41384921132698
15340104188807
-13730494699911
-49544113109053
-13730763136607
15340065374700
-13730897538201
-17118548613921
15340115180511
GG
-41384542096059
1534095454059...

result:

ok 200000 lines

Test #10:

score: 0
Accepted
time: 35ms
memory: 25416kb

input:

10000
7 53
-49257878340663 65913602617244 -77586447275975 37912663831730 -29965751459870 -24028915786606 -20711244730875
6 5
6 7
3 6
5 4
5 2
1 7
1 2 1 -902483856
2 2 0 -166019888
1 2 6 773740058
1 7 4 332162805
3 4 483966804
2 1 8 -161176455
2 6 2 999609920
2 2 1 575504367
1 2 2 -125436309
1 7 6 -85...

output:

-29966653943726
65913436597356
GG
GG
37913147798534
65913275420901
65914275030821
65914850535188
37913860795690
GG
65915321019354
65915455681128
65915560380329
65915183127659
65914812218108
65915548812492
65916224155305
65915243014798
-20710396693949
GG
65915329685860
65915917517754
65915625807955
6...

result:

ok 200000 lines

Test #11:

score: 0
Accepted
time: 32ms
memory: 28280kb

input:

10000
10 4
71797802165245 -54234031880796 29183815458453 29504172959957 49372193603523 -16185389362615 39453295094243 663036651923 96744787191200 -50620611104201
3 4
3 8
5 10
8 1
6 2
7 6
10 3
8 9
5 7
3 10 272721546
2 10 4 618153907
3 8 763987349
1 9 7 870230974
10 8
-13468051963531 -33479821641433 9...

output:

49372466325069
96745405345107
96746169332456
-54231506787020
91247244061845
91246513437933
-33254303623674
-34062728633884
38205426400070
91082413811192
-13468602472782
GG
86995519872619
10278075155744
86995188030179
86995444966527
19338147521978
86995117144520
86994756220490
19337573163350
-9437093...

result:

ok 200000 lines

Test #12:

score: 0
Accepted
time: 2166ms
memory: 57916kb

input:

5
100000 10278
-33062210930377 -27859969846302 -17580975150961 82421468622525 73124685670220 24605270582441 -85306160207816 -94488582195355 85451638721967 61110610044303 20119327748559 28059853591446 40777043818126 -26083158668773 -86932609818311 -80046664707280 36276301345898 72062141434820 -521113...

output:

99730096363045
-53142619895885
62633703474374
91065884890424
95913832039203
71963014593268
-73718672703414
88512243346245
95865153100847
20076236503631
-34284711719410
39055157031710
89757297384484
10950553757520
74269720205379
-9148723701106
-8854522652340
30148659190315
43163551215290
403669992467...

result:

ok 200000 lines

Test #13:

score: 0
Accepted
time: 3311ms
memory: 79484kb

input:

2
200000 23147
-97882461219103 4406360045230 -36834806355299 -23973944052222 67113212265469 11669200972710 -6141709659817 -49560474741369 -18057145741204 -44040958119516 3611153759432 -22756796992893 65910580696453 -78071204736196 25214500077730 -40055869810099 52016133250624 24245766969509 -8573710...

output:

-84299253303082
91895293630648
98660521022574
99046915140773
96940400761168
-80640388829817
62170787931699
80755385476426
87313515284587
58038098598906
58552202132101
69717429372059
50840268036882
49052127297522
30321746138445
57233008189011
-26057525271228
98121546101640
88622027455733
621912032228...

result:

ok 200000 lines

Test #14:

score: 0
Accepted
time: 1430ms
memory: 42844kb

input:

10
50000 1687
36077001037650 -28672159307004 -49567820178173 -66598809699217 51717647349268 40388708770673 -41615842513164 20640893046085 55244284371739 -12659258787859 -57804698295568 -1343921361566 -31490537070370 87398926700957 6369486949134 29314854271472 87863569527089 713709747605 -57348496935...

output:

99530565733478
52005604713243
95506513999163
99658832110191
99907096903163
97154724606255
81337070881934
58949958650580
99715077145772
85133043445758
74581069634085
50184582656147
69809426118622
70927902639147
-91729966293446
17060316600613
-10509867546560
-87583239449605
65152989953561
700189739274...

result:

ok 200000 lines

Test #15:

score: 0
Accepted
time: 126ms
memory: 27316kb

input:

500
1000 92
-34961255282319 -28048065121777 48403085782275 59825930674807 -81890804792913 -3718001248779 -16547933440271 86250915241917 86924443194023 -9735258000336 -91234968422024 -28592966984694 52777768205476 -93185139144600 5318140881411 -56116796281200 9179306895895 -22296214888774 -9108202485...

output:

4668320585308
88059957249898
71176226537037
93851532152750
-32706642031920
99121476057172
79602129082988
84325004453053
86250139584500
98672885845344
45802895326473
68661280872768
97371517369487
93616500614156
27589386746356
88059626048731
99121271376424
68093790136715
99361085683130
98488054170870
...

result:

ok 200000 lines

Test #16:

score: -100
Wrong Answer
time: 651ms
memory: 58504kb

input:

5
100000 10278
-33062210930377 -27859969846302 -17580975150961 82421468622525 73124685670220 24605270582441 -85306160207816 -94488582195355 85451638721967 61110610044303 20119327748559 28059853591446 40777043818126 -26083158668773 -86932609818311 -80046664707280 36276301345898 72062141434820 -521113...

output:

-12749974258479
84017004006248
-89539813077621
-80338381552172
82312582262422
98103687339070
94560175951271
93134724507461
58620904163291
81867438963191
-400987364342
63575768373779
90005411398068
-98825155078969
67966851202993
98296098861174
-24807695936092
96949416015307
-34263626970319
8507072303...

result:

wrong answer 186th lines differ - expected: '99973826320857', found: '99683320589733'