QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#717693#9492. 树上简单求和sunrise10245 61ms43124kbC++144.0kb2024-11-06 18:43:112024-11-06 18:43:12

Judging History

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

  • [2024-11-06 18:43:12]
  • 评测
  • 测评结果:5
  • 用时:61ms
  • 内存:43124kb
  • [2024-11-06 18:43:11]
  • 提交

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=1;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: 5
Accepted

Test #1:

score: 5
Accepted
time: 61ms
memory: 40956kb

input:

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

output:

12105153858659381124
18367442707572066757
11668241962484097878
11288238120352358472
1742468310074622166
9942835997686093671
3305677510569607477
17741602000425004088
14984128302052618266
1075081718074605786
6509217537832509095
16750513627843273113
8569443169249732820
14475184194298579044
156111071108...

result:

ok 3000 lines

Test #2:

score: 5
Accepted
time: 59ms
memory: 39012kb

input:

3000 3000
1612333876155866602 8538417838700679227 6080765231437578796 17905224638340228394 12270907925903144224 17944105326358594564 17302041033966840611 1006351124625222126 496336153231744288 9393087977687876980 9553975238547373621 9361882717200384390 15051881329169144319 9757999873162420435 882725...

output:

11133131376095771981
7909873024850695144
16250639243139481926
14562550655578101207
8274205996508264973
178549413271904466
2368406276743327913
7464009386554813982
9439464815411774627
1471756740732097060
15201641099137019227
6774030298556871576
18156105511913219667
1553508745644446823
4225137078364117...

result:

ok 3000 lines

Test #3:

score: 5
Accepted
time: 49ms
memory: 39020kb

input:

3000 3000
9709246061666095435 1861649101703072889 10620139893353930613 17635186539135419482 710209455559527146 6075101384669982511 1120305006358459674 9703156967435388252 1397046737759839382 5259056712870179169 8253156305433022999 710199693203327302 15130650033641744675 10720111924616886955 15543351...

output:

7834604406305153073
5037061270969117785
16481572776620825702
15177894197606565804
3120320619896892806
18008650876379132344
7417108723176816402
13515164814425439399
3299769942258542105
15897528270699011770
11642805469843844638
16764682282380318054
4824039114054405772
4859834102876213962
1234210473247...

result:

ok 3000 lines

Test #4:

score: 5
Accepted
time: 52ms
memory: 43124kb

input:

3000 3000
16538965545220923528 18062192327708400751 10422465150728338588 3471522151129113073 1236650672072793692 1942240200040301168 13090729759591037952 15335798523677372669 9912100622761466753 11177948788405690381 3710859061697501523 4984944638666762977 17278589713462878008 6371292801024547050 868...

output:

8182453933067329108
13535217473847106938
17067385337010269798
3806121648880466130
11322569288575153037
11079197311131660121
9670138330007803226
6554062218199796758
965954569567598779
18055887214749050688
6142620503089407421
8690117812667761187
9547139298346295115
8890987597519353054
1755036654049586...

result:

ok 3000 lines

Test #5:

score: 5
Accepted
time: 51ms
memory: 41208kb

input:

3000 3000
17759588706587888497 10550000524636484378 11601004513528075994 7150322911283804521 4459707248078569712 10692395730842402625 8940418793863522991 12967068928670540447 9954278250450015940 13702413838608801301 10598390500439869870 15110245227553613794 490862872212325709 15164980555660957366 94...

output:

9743736929788175512
16812303667256960040
14694223512340829897
550204232580650311
1175342872438242313
17622261358285047637
7413682703975031220
12643066512274062227
1868985217436232595
5471830334855681322
8070132260376389587
3970361922096052085
218281824643752746
991917103472727104
2960248244218479023...

result:

ok 3000 lines

Subtask #2:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Test #6:

score: 12
Accepted
time: 5ms
memory: 38624kb

input:

5 7
0 3 2 6 4
1 2
2 4
1 5
5 3
3 4
4 2
2 5
5 1
5 3 0
3 2 5
4 4 4
4 4 3
5 2 0
3 4 3
5 5 6

output:

15
21
10
13
17
26
18

result:

ok 7 lines

Test #7:

score: 0
Time Limit Exceeded

input:

70000 70000
3805295436278888199 9842309351516174725 1566744796319231180 2206519284152256579 2715928675931950447 6346821976624501261 16020972671480798719 14702021753902144915 17127828773798978442 15779168055669690475 4964561323934614661 9395102787554964450 6377076753365184543 15167378195767668817 288...

output:

5971729064136092190
6457394048987305727
13604212649915736394
8639973959364892219
437861319070967556
16133076880026962355
5384937395694479961
4591478439775690843
16071919565966962790
15485626634068969082
10235993901046758372
3449528613427081475
8064280362779764074
12784984512326434905
424951714880051...

result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Time Limit Exceeded

Test #21:

score: 0
Time Limit Exceeded

input:

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

output:

9042998055336671259
11611293489264521142
5835924579879681322
9187084356907537870
17810346410706951073
565636160725988981
837626748701483168
16059573289829807099
7246210357888652619
7725251776483176497
17088098442183693937
9042305714006927228
10907378739216215456
6526772063609981609
51578202456469609...

result:


Subtask #5:

score: 0
Time Limit Exceeded

Test #27:

score: 0
Time Limit Exceeded

input:

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

output:

11479812171669345085
7612644482907856514
7664363696211351499
10419050713553268082
7115244954460011045
9683711549165598600
15714069303067445091
5098969076555779384
17312050420753525411
13302302653999024684
15237835478514966949
1011923303415334401
15280591493481885526
11613220426756932450
109080667232...

result:


Subtask #6:

score: 0
Time Limit Exceeded

Test #34:

score: 0
Time Limit Exceeded

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:


Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%