QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#717544#9492. 树上简单求和sunrise102419 3930ms105540kbC++144.0kb2024-11-06 18:16:152024-11-06 18:16:15

Judging History

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

  • [2024-11-06 18:16:15]
  • 评测
  • 测评结果:19
  • 用时:3930ms
  • 内存:105540kb
  • [2024-11-06 18:16:15]
  • 提交

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;
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[K];
ull cn[K][K];
ull s[K];
int kid[N];
int B;
int l[K],r[K];
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]]+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;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 37ms
memory: 34928kb

input:

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

output:

9383413186378873116
3095581167033035614
3808639205880416252
11787830353141245625
14961926795317581787
13404557921112348503
192090132725882489
17454762610169269729
14828554941186784233
4536803641500860618
1281931949365917100
15389643291703019109
7995004456154100328
4438152969602344392
541095779786650...

result:

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

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: 3066ms
memory: 93628kb

input:

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

output:

9397312230894620832
11447443369478712750
13191922051752074981
18138643683748015393
17670732325422875118
15293512441821650152
13637610636193512483
11016216921404599271
13568296293154590075
7473823146490356818
7580358626639442564
7033912465279505129
10714877700550693778
10263320216247528949
8373804189...

result:

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

Subtask #5:

score: 0
Wrong Answer

Test #27:

score: 0
Wrong Answer
time: 3930ms
memory: 99392kb

input:

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

output:

1329130864668319333
7612644482907856514
7664363696211351499
10419050713553268082
15411307721168536909
17979774315874124464
5563387996066419339
13395031843264305248
17312050420753525411
3151621346997998932
15237835478514966949
1011923303415334401
15280591493481885526
11613220426756932450
757385416258...

result:

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

Subtask #6:

score: 19
Accepted

Test #34:

score: 19
Accepted
time: 2235ms
memory: 105304kb

input:

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

output:

5519324519442957729
13462861144392030499
8898301730697138469
4148979398311169421
15090246851327208067
8628707816538336707
13867297907038176506
10296428352441857103
15654304415409320656
7404566644919251615
9870876264015800597
6356224262148620783
249874952637342736
9023132497407647441
1416175985367538...

result:

ok 200000 lines

Test #35:

score: 19
Accepted
time: 2089ms
memory: 103940kb

input:

200000 200000
11863650499568632095 6646669915142734572 4053375998669045948 14662364203830894482 7319511971537928619 4131498054494361157 7103043576860354080 2730587527012777841 8626012955062792888 7098277606750148625 12990209623538415680 100871355087529915 12267084290544303817 7008468684400973426 856...

output:

11796827338356402281
853302424664654652
564419876379363056
11173501553976506440
2595891684253320024
5590778053561483334
16613470245879883493
5698255402711241072
8125718572356459513
11371252602486101178
7605800585391618993
17939653588292877927
15906636118593883045
14840423959426947118
122409373008752...

result:

ok 200000 lines

Test #36:

score: 19
Accepted
time: 2139ms
memory: 102532kb

input:

200000 200000
7819034666999754227 1261434745131385029 4729051582132640442 9603230030483067185 9188148629137054368 4647584887897271213 14878584596185020248 5036501082632549589 13434605396022727436 10747373329537943689 2859138487129973374 17399126170759425906 5170686633178482234 1548518177806164267 68...

output:

13979872615900358449
13089809959604496472
1561607543806976909
704865086165131395
4750114500765789463
8620101000132483891
1061990993707638791
8219417779659049453
16783172337878697026
731502258552473136
15516870835064396649
13412140913912394465
5029558179142432386
9655856473800271062
14498308915283050...

result:

ok 200000 lines

Test #37:

score: 19
Accepted
time: 2144ms
memory: 103920kb

input:

200000 200000
13667364256171297683 5643454264481609425 13916992424255487273 16139471110620927446 10964822257543206396 18104319795931117637 6754294313610492941 627150985476406559 9787453073837140391 8330282299925244302 16457178623381098023 2644823686047461659 3971198924127091796 9747389824949735337 1...

output:

11367465309833674818
18362877133708215281
7423548724337603968
8957456044849213851
17833913066069915980
7858235162317128668
12543057704351927321
10505054748074388644
6816176482433035300
2467436539272277421
1679282916199502250
4514431222303891247
8020348968469583082
4250522620562980350
344143146282723...

result:

ok 200000 lines

Test #38:

score: 19
Accepted
time: 1909ms
memory: 105072kb

input:

200000 200000
8264785020939323331 5620958879723030311 933008402364228745 5711653520387260744 16167130674961631916 10635243671618608635 7034482071437480120 10254956504177159052 10510387087831623788 8381634740474427698 9506597691312026965 14784451691298216046 15821757099494287606 1919888068508281591 1...

output:

5787014875832445646
9634577796009446262
12314294073540302873
2915216425908688602
7120463906657998875
4286046781319255714
6776880553034928756
7781782119312943753
10261843991161497641
6413565360321098258
15025688638596291097
9526784383328827422
4012177064000612489
1287077077700121461
98702777920648956...

result:

ok 200000 lines

Test #39:

score: 19
Accepted
time: 1960ms
memory: 104196kb

input:

200000 200000
11664667196988092805 1811572170904050995 15694419630875459125 12737549840477675073 16755302998318006416 4014818780481352253 5609118000649893828 6256332194728466258 15733576495075669968 17960532384856428505 15897732465031414620 17425753576410476171 4620624862371502705 112264419736513372...

output:

6480474289914832244
5686011217288555755
14160731859453855234
17554436276709117739
2341367826083254204
8545580044567165676
264741062779916095
3300445074446425091
1133253489203829542
15906618027983611292
4617068730941954223
9183813939934374009
17667722659841632674
17058280131349615456
5995389694319663...

result:

ok 200000 lines

Test #40:

score: 19
Accepted
time: 1982ms
memory: 105144kb

input:

200000 200000
1537940886958943461 9001579450047645548 5527298164056925772 15445874594277229387 11547996012713764596 2685142508745516922 15898551218448062337 16566357055814699599 15778851736432174335 10222916087451023672 14639095824490451029 13130899683058695675 2954207938828868462 150325623383373666...

output:

6794024285749225899
15444253183026756906
16252225983581025191
18270054647591833460
14669804966517502833
7889126920459519979
11162985402720101082
6093427967053788994
10568703419124160247
10842018941076619829
12114458223856608006
16611571295135208112
6660992456255029750
14854289142138250053
8448421034...

result:

ok 200000 lines

Test #41:

score: 19
Accepted
time: 1978ms
memory: 105540kb

input:

200000 200000
9312450956088465409 13091411438344500136 13533801408631028803 397220365455228788 9050318983523848941 14099016315633088068 17718824544128458130 18224580765371017222 16359847342241893914 6209442109030804295 8140737573685484628 16329892452717577856 12435238272437023209 1214903064014288477...

output:

17881136615169673858
10075746974396262535
1101717753396811008
11092187645455964376
312406901260616120
15269190090424605570
16293852523769965660
7287397773622456008
12586683442681630396
10525460771223157010
16483491603350167181
5677129374080663282
17770626863503596216
16241388034502960475
16358076653...

result:

ok 200000 lines

Subtask #7:

score: 0
Skipped

Dependency #1:

0%