QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#717724#9492. 树上简单求和sunrise10240 5032ms102540kbC++144.3kb2024-11-06 18:48:272024-11-06 18:48:28

Judging History

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

  • [2024-11-06 18:48:28]
  • 评测
  • 测评结果:0
  • 用时:5032ms
  • 内存:102540kb
  • [2024-11-06 18:48:27]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
const int N=4e5+5;
const int K=700;
const int M=N/K+5;
int n,m;
ull a[N];
int cn1,cn2;
int tp1[N],tp2[N];
int in1[N],out1[N],in2[N],out2[N];
vector<int> e1[N],e2[N];
int d1[N],d2[N];
int f1[N][20];
int f2[N][20];
ull val[N];
ull tag[M];
ull cn[M][M];
ull s[M];
int kid[N];
int B;
int l[M],r[M];
void dfs1(int no,int fa){
    d1[no]=d1[fa]+1;
    f1[no][0]=fa;
    for(int i=1;i<20;++i)f1[no][i]=f1[f1[no][i-1]][i-1];
    in1[no]=++cn1;
    tp1[cn1]=no;
    for(int to:e1[no]){
        if(to==fa)continue;
        dfs1(to,no);
    }
    out1[no]=++cn1;
    tp1[cn1]=-no;
}
void dfs2(int no,int fa){
    d2[no]=d2[fa]+1;
    f2[no][0]=fa;
    for(int i=1;i<20;++i)f2[no][i]=f2[f2[no][i-1]][i-1];
    in2[no]=++cn2;
    tp2[cn2]=no;
    for(int to:e2[no]){
        if(to==fa)continue;
        dfs2(to,no);
    }
    out2[no]=++cn2;
    tp2[cn2]=-no;
}
int lca1(int x,int y){
    if(d1[x]<d1[y])swap(x,y);
    for(int i=19;i>=0;--i){
        if(d1[f1[x][i]]>=d1[y])x=f1[x][i];
    }
    if(x==y)return x;
    for(int i=19;i>=0;--i){
        if(f1[x][i]!=f1[y][i]){
            x=f1[x][i];
            y=f1[y][i];
        }
    }
    return f1[x][0];
}
int lca2(int x,int y){
    if(d2[x]<d2[y])swap(x,y);
    for(int i=19;i>=0;--i){
        if(d2[f2[x][i]]>=d2[y])x=f2[x][i];
    }
    if(x==y)return x;
    for(int i=19;i>=0;--i){
        if(f2[x][i]!=f2[y][i]){
            x=f2[x][i];
            y=f2[y][i];
        }
    }
    return f2[x][0];
}
void add(int x,ull d){
    if(!x)return;
    for(int i=1;i<kid[x];++i){
        tag[i]+=d;
    }
    for(int i=l[kid[x]];i<=x;++i){
        val[i]+=d;
        const int id=(tp1[i]>0?tp1[i]:-tp1[i]);
        if(tp1[i]>0){
            s[kid[in2[id]]]+=d;
            s[kid[out2[id]]]-=d;
        }
        else{
            s[kid[in2[id]]]-=d;
            s[kid[out2[id]]]+=d;
        }
    }
}
ull qu(int x){
    if(!x)return 0;
    ull sum=0;
    //for(int i=1;i<kid[x];++i)sum+=s[i];
    for(int i=1;i<=B;++i){
        sum+=tag[i]*cn[kid[x]-1][i];
    }
    for(int i=l[kid[x]];i<=x;++i){
        const int id=(tp2[i]>0?tp2[i]:-tp2[i]);
        if(tp2[i]>0){
            sum+=val[in1[id]];
            sum-=val[out1[id]];
        }
        else{
            sum-=val[in1[id]];
            sum+=val[out1[id]];
        }
    }
    for(int i=l[kid[x]];i<=x;++i){
        const int id=(tp2[i]>0?tp2[i]:-tp2[i]);
        if(tp2[i]>0){
            sum+=val[in1[id]]+tag[kid[in1[id]]];
            sum-=val[out1[id]]+tag[kid[out1[id]]];
        }
        else{
            sum-=val[in1[id]]+tag[kid[in1[id]]];
            sum+=val[out1[id]]+tag[kid[out1[id]]];
        }
    }
    return sum;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%llu",&a[i]);
    }
    for(int i=1;i<n;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        e1[u].push_back(v);
        e1[v].push_back(u);
    }
    for(int i=1;i<n;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        e2[u].push_back(v);
        e2[v].push_back(u);
    }
    dfs1(1,0);
    dfs2(1,0);
    B=(cn1-1)/K+1;
    for(int i=1;i<=B;++i){
        l[i]=r[i-1]+1;
        r[i]=i*K;
    }
    r[B]=cn1;
    for(int i=1;i<=B;++i){
        for(int j=l[i];j<=r[i];++j){
            kid[j]=i;
        }
    }
    for(int i=1;i<=B;++i){
        for(int j=1;j<=B;++j)cn[i][j]=cn[i-1][j];
        for(int j=l[i];j<=r[i];++j){
            const int id=(tp2[j]>0?tp2[j]:-tp2[j]);
            if(tp2[j]>0){
                cn[i][kid[in1[id]]]++;
                cn[i][kid[out1[id]]]--;
            }
            else{
                cn[i][kid[in1[id]]]--;
                cn[i][kid[out1[id]]]++;
            }
        }
    }
    for(int i=1;i<=n;++i){
        val[in1[i]]=a[i];
        s[kid[in2[i]]]+=a[i];
    }
    while(m--){
        int x,y;
        ull k;
        scanf("%d%d%llu",&x,&y,&k);
        int lc=lca1(x,y);
        add(in1[x],k);
        add(in1[y],k);
        add(in1[lc],-k);
        add(in1[f1[lc][0]],-k);
        lc=lca2(x,y);
        printf("%llu\n",qu(in2[x])+qu(in2[y])-qu(in2[lc])-qu(in2[f2[lc][0]]));
    }
    return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 28ms
memory: 38980kb

input:

3000 3000
7236742292501328495 17973811477309806363 16075782662531676171 17971236571771878676 11392080645527132110 3685563455925680459 9773593720088356683 8313828403245053795 7736401634567449043 1634817828009987181 6951124933529719486 12775126714635387213 15460977209223753216 397573676785925632 31372...

output:

7661482954925656803
7884569729117809968
4730448276649661938
4372702632079024906
3673592163387707296
6766434970900239011
9024911951171439229
2069699732718945623
13628043964698436962
5442416998171026151
8316450305550929156
5681520216709208516
13267310100493814693
18414491044573544072
10964531166256013...

result:

wrong answer 1st lines differ - expected: '12105153858659381124', found: '7661482954925656803'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #21:

score: 0
Wrong Answer
time: 3774ms
memory: 92140kb

input:

200000 200000
622783158027686223 2242697872372232537 8481648430436878777 10092474834140799044 15403999682625301609 12614289513474949582 9180944589267018841 7823784919308285798 8257785171198951273 5134508521895120821 8041682272181381093 3835432206618893170 2653803171409877650 5589823419153460372 1007...

output:

9147824207425865134
3249435975002786223
8519910141364119343
16759925070994672599
2885741580786544918
18241149490488464416
12659929201104984415
13698421013491819342
150862013117312590
7525298558765569221
6673501141549133609
8657208925453928532
14477587614238508739
3128049581690961898
1554730129440051...

result:

wrong answer 1st lines differ - expected: '9042998055336671259', found: '9147824207425865134'

Subtask #5:

score: 0
Wrong Answer

Test #27:

score: 0
Wrong Answer
time: 5032ms
memory: 99972kb

input:

200000 200000
1958469220619413759 14991498002015735322 6054491201406941902 18206143187746582567 15082377615826460430 2936248617457291604 10073577150351675920 16534472678586906457 2207599132486246393 10301540360769075442 1492580560381080472 551692353431379140 13238280352539145808 8462626987240986565 ...

output:

3673745359943198606
4760882764966025886
12971992686641277240
10544009267013291876
3552786699617091664
15899555036778913980
3311866370665610570
5398213694893717765
1926547487459938868
18000477484564263404
12914618996455469509
15244583680205434939
3925719320520810860
9953315692799731383
39549807745448...

result:

wrong answer 1st lines differ - expected: '11479812171669345085', found: '3673745359943198606'

Subtask #6:

score: 0
Wrong Answer

Test #34:

score: 0
Wrong Answer
time: 2677ms
memory: 102540kb

input:

200000 200000
6794776813641982926 1561596256197101737 10910039723053043515 7892247858295192798 12233819960547881004 17695389034783066733 9173201689566865598 17626618141377486739 7358781671024283919 6787559733384974662 3884392438269280436 14872846228351316833 9037842441501571648 14299818404271084016 ...

output:

3087596776361039973
2555933051991711359
11880662586147114455
17688212090841349554
9849974654588478798
13343533897599523871
13026396384188650130
7784524724403928228
5278038875050623056
5565774504782469270
17343831267704716247
2051782488789171546
7651722543348872379
10565008204257151114
20995361815341...

result:

wrong answer 1st lines differ - expected: '5519324519442957729', found: '3087596776361039973'

Subtask #7:

score: 0
Skipped

Dependency #1:

0%