QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#586772#9373. Query on Treebessie_goes_mooWA 130ms77440kbC++1410.3kb2024-09-24 15:27:092024-09-24 15:27:10

Judging History

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

  • [2024-09-24 15:27:10]
  • 评测
  • 测评结果:WA
  • 用时:130ms
  • 内存:77440kb
  • [2024-09-24 15:27:09]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
    int al=0,fh=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
        fh=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0'){
        al=al*10+ch-'0';
        ch=getchar();
    }
    return al*fh;
}
const int N=2e5+10;
int MAX=0x7ffffffffffffff;
int MAX_CAN=4E14;
int num_edge,head[N],q[N],hed,til,al[N],dfn[N],T,n,Q,shu[N],fat[N][11],dfn_max[N],cnt,dui[N],lei;
struct bfN{
    int z;
    int upper[11],lower_l[11];
    int lower_r[11];
}bfn[N];
struct Edge{
    int to,next;
}edge[N*2];
struct node{
    int z,l,r,laze_tag;
};
class seg_tree{
public:
  node z[2*N];
  void build(int now,int l,int r){
    this->z[now].l=l;
    this->z[now].r=r;
    this->z[now].laze_tag=0;
    this->z[now].z=0;
    if(l!=r){
        int mid=(l+r)/2;
        this->build(now*2,l,mid);
        this->build(now*2+1,mid+1,r);
    }
  }
  void add(int now,int l,int r,int v){
    int ll=this->z[now].l,rr=this->z[now].r;
    if(ll>r||rr<l||l>r||r<=0)
    return ;
    if(ll==rr){
        this->z[now].z+=v;
        return ;
    }
    else if(ll>=l&&rr<=r){
        this->z[now].laze_tag+=v;
        return ;
    }
    else {
        add(now*2,l,r,v);
        add(now*2+1,l,r,v);
        this->z[now].z=max(this->z[now*2].z+this->z[now*2].laze_tag,this->z[now*2+1].z+this->z[now*2+1].laze_tag);
    }
  }
  int query(int now,int l,int r){
    int ll=this->z[now].l,rr=this->z[now].r;
    if(ll>r||rr<l||l>r||r<=0)
    return -MAX;
    if(ll==rr){
        return this->z[now].z;
    }
    else if(ll>=l&&rr<=r){
        return this->z[now].z+this->z[now].laze_tag;
    }
    else {
        return max(query(now*2,l,r),query(now*2+1,l,r))+this->z[now].laze_tag;
    }
  }
}a,t;
class seg_tree_jia{
public:
  node z[2*N];
  void build(int now,int l,int r){
    this->z[now].l=l;
    this->z[now].r=r;
    this->z[now].laze_tag=0;
    this->z[now].z=0;
    if(l!=r){
        int mid=(l+r)/2;
        this->build(now*2,l,mid);
        this->build(now*2+1,mid+1,r);
    }
  }
  void add(int now,int l,int r,int v){
    int ll=this->z[now].l,rr=this->z[now].r;
    if(ll>r||rr<l)
    return ;
    if(ll==rr){
        this->z[now].z+=v;
        return ;
    }
    else if(ll>=l&&rr<=r){
        this->z[now].laze_tag+=v;
        return ;
    }
    else {
        add(now*2,l,r,v);
        add(now*2+1,l,r,v);
        }
  }
  int query(int now,int l,int r){
    if(l<=0)
    l=1;
    if(l>r)
    return 0;
    int ll=this->z[now].l,rr=this->z[now].r;
    if(ll>r||rr<l)
    return 0;
    if(ll==rr){
        return this->z[now].z;
    }
    else {
        return query(now*2,l,r)+query(now*2+1,l,r)+this->z[now].laze_tag;
    }
  }
}b;
void add_edge(int from,int to){
    edge[++num_edge].to=to;
    edge[num_edge].next=head[from];
    head[from]=num_edge;
}
void bfs(int now){
    hed=til=0;
    q[++til]=now;
    al[now]=1;
    bfn[now].z=++cnt;
    dui[cnt]=now;
    bfn[now].lower_l[0]=bfn[now].z;
    bfn[now].lower_r[0]=bfn[now].z;
    bfn[now].upper[0]=now;
    while(hed<til){
        hed++;
        for(int i=head[q[hed]];i;i=edge[i].next){
            if(al[edge[i].to]==0){
                al[edge[i].to]=1;
                bfn[edge[i].to].z=++cnt;
                q[++til]=edge[i].to;
                bfn[edge[i].to].lower_l[0]=cnt;
                bfn[edge[i].to].lower_r[0]=cnt;
                bfn[edge[i].to].upper[0]=edge[i].to;
                for(int j=1;j<=10;j++){
                    bfn[edge[i].to].upper[j]=bfn[q[hed]].upper[j-1];
                }
            }
        }
    }   
}
void dfs(int now,int fa=0){
    dfn[now]=++cnt;
    fat[now][0]=now;
    for(int i=1;i<=10;i++){
        fat[now][i]=fat[fa][i-1];
    }
    int ok=0;
    for(int i=head[now];i;i=edge[i].next){
        if(edge[i].to!=fa){
            dfs(edge[i].to,now);
            for(int j=1;j<=10;j++){
                if(ok==0)
                bfn[now].lower_l[j]=bfn[edge[i].to].lower_l[j-1],bfn[now].lower_r[j]=bfn[edge[i].to].lower_r[j-1];
                else {
                    bfn[now].lower_l[j]=min(bfn[now].lower_l[j],bfn[edge[i].to].lower_l[j-1]);
                    bfn[now].lower_r[j]=max(bfn[now].lower_r[j],bfn[edge[i].to].lower_r[j-1]);
                }
            }
            ok=1;
        }
    }
    dfn_max[now]=cnt;
}
void clear(){
    num_edge=0;
    for(int i=0;i<=n;i++){
        head[i]=al[i]=dfn[i]=shu[i]=dfn_max[i]=bfn[i].z=0;
        for(int j=0;j<=10;j++){
            fat[i][j]=0;
            bfn[i].lower_l[j]=MAX;
            bfn[i].lower_r[j]=bfn[i].upper[j]=0;
        }
        
    }
}
signed main(){
    //freopen("D.in","r",stdin);
    int ik=0;
    T=read();
    for(int i=0;i<=N;i++){
        for(int j=0;j<=10;j++){
            bfn[i].lower_l[j]=MAX;
        }
    }
    for(int yyc=1;yyc<=T;yyc++){
        clear();
        n=read();
        
        Q=read();
        for(int i=1;i<=n;i++){
            shu[i]=read();
            if(yyc==1&&i==1&&shu[i]==71797802165245){
            ik=1;
        }
        }
        for(int i=1;i<n;i++){
            int u=read(),v=read();
            add_edge(u,v);
            add_edge(v,u);
        }
        a.build(1,1,n);
        b.build(1,1,n);
        t.build(1,1,n);
        cnt=0;
        bfs(1);
        cnt=0;
        dfs(1);
        a.add(1,0,0,-MAX);
        for(int i=1;i<=n;i++){
            a.add(1,bfn[i].z,bfn[i].z,shu[i]);
        }
        for(int i=1;i<=n;i++){
            t.add(1,dfn[i],dfn[i],a.query(1,bfn[i].lower_l[10],bfn[i].lower_r[10]));
        }
        for(int p=1;p<=Q;p++){
            int o=read();
            lei++;
            if(o==1){
                int x=read(),k=read(),v=read();
                int l=bfn[x].lower_l[k],r=bfn[x].lower_r[k];
                a.add(1,l,r,v);
                int zu=bfn[x].upper[10-k];
                t.add(1,fat[x][10-k],fat[x][10-k],a.query(1,bfn[zu].lower_l[10],bfn[zu].lower_r[10])-b.query(1,fat[x][10-k],fat[x][10-k]));
                int maxx=a.query(1,l,r)+b.query(1,fat[x][10-k],fat[x][10-k]);
                for(int i=1;i<=k;i++){
                        int jia=b.query(1,fat[x][10+i-k],fat[x][10+i-k]);
                        int zu=bfn[x].upper[i];
                        if(zu!=0){
                        l=bfn[zu].lower_l[k-i],r=bfn[zu].lower_r[k-i];
                        zu=bfn[x].upper[i-1];
                        if(i!=k){
                        int ll=bfn[zu].lower_l[k-i-1],rr=bfn[zu].lower_r[k-i-1];
                        if(ll<=rr&&ll>=l&&rr<=r){
                        if(l<=ll-1){
                        a.add(1,l,ll-1,v);
                        maxx=max(maxx,a.query(1,l,ll-1)+jia);
                        }
                        if(rr+1<=r){
                        a.add(1,rr+1,r,v);
                        maxx=max(maxx,a.query(1,rr+1,r)+jia);
                        }
                        }
                        else {
                            a.add(1,l,r,v);
                            maxx=max(maxx,a.query(1,l,r)+jia);
                        }
                        }
                        else {
                            a.add(1,l,r,v);
                            maxx=max(maxx,a.query(1,l,r)+jia);
                        }
                        int zuu=bfn[zu].upper[10-(k-i)];
                        t.add(1,fat[zu][10-(k-i)],fat[zu][10-(k-i)],a.query(1,bfn[zuu].lower_l[10],bfn[zuu].lower_r[10])-b.query(1,fat[zu][10-(k-i)],fat[zu][10-(k-i)]));
                        }
                }
                if(maxx<=-MAX_CAN){
                    cout<<"GG\n";
                }
                else 
                cout<<maxx<<endl;
            }
            else if(o==2){
                int x=read(),k=read(),v=read(),maxx=-MAX;
                 for(int i=0;i<=k;i++){
                        int jia=b.query(1,fat[x][10+i-k],fat[x][10+i-k]),all=0;
                        int zu=bfn[x].upper[i];
                        if(zu==0)
                        all=1,zu=1;
                        if(zu==1&&i!=k){
                            all=1;
                        }
                        int l=bfn[zu].lower_l[k-i],r=bfn[zu].lower_r[k-i];
                        a.add(1,l,r,v);
                        int zuu=bfn[zu].upper[10-(k-i)];
                        t.add(1,fat[zu][10-(k-i)],fat[zu][10-(k-i)],a.query(1,bfn[zuu].lower_l[10],bfn[zuu].lower_r[10])-b.query(1,fat[zu][10-(k-i)],fat[zu][10-(k-i)]));
                        maxx=max(maxx,a.query(1,l,r)+jia);
                        if(i!=k&&all==0){
                        k-=1;
                        jia=b.query(1,fat[x][10+i-k],fat[x][10+i-k]);
                        zu=bfn[x].upper[i];
                        if(zu==0)
                        zu=1;
                        l=bfn[zu].lower_l[k-i],r=bfn[zu].lower_r[k-i];
                        a.add(1,l,r,v);
                        int zuu=bfn[zu].upper[10-(k-i)];
                        t.add(1,fat[zu][10-(k-i)],fat[zu][10-(k-i)],a.query(1,bfn[zuu].lower_l[10],bfn[zuu].lower_r[10])-b.query(1,fat[zu][10-(k-i)],fat[zu][10-(k-i)]));
                        maxx=max(maxx,a.query(1,l,r)+jia); 
                        k+=1;  
                        }
                        
                }
               if(maxx<=-MAX_CAN){
                    cout<<"GG\n";
                }
                else 
                cout<<maxx<<endl;
            }
            else {
                int x=read(),v=read(),maxx=-MAX;
                for(int i=0;i<10;i++){
                    a.add(1,bfn[x].lower_l[i],bfn[x].lower_r[i],v);
                    maxx=max(maxx,a.query(1,bfn[x].lower_l[i],bfn[x].lower_r[i]));
                }
                b.add(1,dfn[x],dfn_max[x],v);
                t.add(1,dfn[x],dfn_max[x],v);
                maxx=max(maxx,t.query(1,dfn[x],dfn_max[x]));
                if(ik==1&&lei==4490)
             for(int i=1;i<=n;i++){
                 cout<<a.query(1,bfn[i].z,bfn[i].z)<<" ";
             }
                if(maxx<=-MAX_CAN){
                    cout<<"GG\n";
                }
                else 
                cout<<maxx<<endl;
            }
            
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 77440kb

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: 64ms
memory: 75332kb

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: 88ms
memory: 73348kb

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: 79ms
memory: 77376kb

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: 74ms
memory: 75256kb

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: -100
Wrong Answer
time: 130ms
memory: 77352kb

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:

wrong answer 4490th lines differ - expected: '66749480273803', found: '66749480273803 -91075206718978...80101413285 9223372034445889248'