QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#684972#9373. Query on TreewyxqwqWA 42ms58316kbC++147.6kb2024-10-28 16:51:482024-10-28 16:51:48

Judging History

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

  • [2024-10-28 16:51:48]
  • 评测
  • 测评结果:WA
  • 用时:42ms
  • 内存:58316kb
  • [2024-10-28 16:51:48]
  • 提交

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
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;
}

struct Seg{
#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)
struct Node{
    ll mx,tag;
    Node(){mx=-inf,tag=0;}
    void upd(ll &k){mx+=k,tag+=k;}
}tr[N<<2];
void ps(int x){tr[x].mx=max(tr[ls].mx,tr[rs].mx);}
void pd(int x){
    ll &k=tr[x].tag;
    tr[ls].upd(k);
    tr[rs].upd(k);
    k=0;
}
void build(ll *a,int x,int l,int r){
    if(l>r) re;
    // printf("build(%d,%d,%d)\n",x,l,r);
    if(l==r){
        tr[x].mx=a[l];
        tr[x].tag=0;
        re;
    }
    build(a,ls,l,mid);
    build(a,rs,mid+1,r);
    ps(x);
}
void update(int x,int l,int r,int L,int R,ll v){
    if(L>R) re;
    // printf("update(%d,%d,%d,%d,%d,%lld)\n",x,l,r,L,R,v);
    if(l>=L&&r<=R){
        tr[x].upd(v);
        re;
    }
    pd(x);
    if(L<=mid) update(ls,l,mid,L,R,v);
    if(R>mid) update(rs,mid+1,r,L,R,v);
    ps(x);
}
void set(int x,int l,int r,int aim,ll v){
    if(l==r){tr[x].mx=v;re;}
    pd(x);
    if(aim<=mid) set(ls,l,mid,aim,v);
    else set(rs,mid+1,r,aim,v);
    ps(x);
}
ll ask(int x,int l,int r,int L,int R){
    if(L>R) re -inf;
    if(l>=L&&r<=R) re tr[x].mx;
    pd(x);
    if(R<=mid) re ask(ls,l,mid,L,R);
    if(L>mid) re ask(rs,mid+1,r,L,R);
    re max(ask(ls,l,mid,L,R),ask(rs,mid+1,r,L,R));
}
};
ll tmp[N];

namespace Tree_b{
Seg b;
void build(){fo(i,1,n) tmp[i]=a[bod[i]];b.build(tmp,1,1,n);}
void update(int l,int r,ll v){b.update(1,1,n,l,r,v);}
ll ask(int l,int r){
    re b.ask(1,1,n,l,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{
Seg tag,mx;
void build(){
    fo(i,1,td) tmp[i]=0;
    tag.build(tmp,1,1,td);
    fo(i,1,n) tmp[i]=-inf;
    fo(i,1,n) if(bR[i][K])
        fo(j,bL[i][K],bR[i][K]) big(tmp[dL[i]],a[bod[j]]);
    mx.build(tmp,1,1,td);
    // 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;
    tag.update(1,1,td,l,r,v);
    mx.update(1,1,td,l,r,v);
}
ll ask(int l,int r){
    re mx.ask(1,1,td,l,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.ask(1,1,td,dL[x],dL[x]));
    tag.set(1,1,td,dL[x],0);
    // tag[dL[x]]=0;
}
void reset(int x){
    mx.set(1,1,td,dL[x],Tree_b::ask(bL[x][K],bR[x][K]));
    // 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;
    // fo(i,0,K) printf("[%d,%d] ",bL[5][i],bR[5][i]);HH;printf("[%d,%d]\n",dL[5],dR[5]);
    Tree_b::build();Tree_d::build();
    // cout<<"mx:";out(Tree_d::mx,1,td);
    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(){
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    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: 58196kb

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: 37ms
memory: 58116kb

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

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:

wrong answer 196th lines differ - expected: '92593553133044', found: '92593120115062'