QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#684586 | #9373. Query on Tree | wyxqwq | WA | 3311ms | 79484kb | C++14 | 5.8kb | 2024-10-28 14:32:54 | 2024-10-28 14:32:54 |
Judging History
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'