QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#717734#9492. 树上简单求和sunrise10240 0ms0kbC++144.3kb2024-11-06 18:50:232024-11-06 18:50:24

Judging History

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

  • [2024-11-06 18:50:24]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-11-06 18:50:23]
  • 提交

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]];
        }
    }
    if(sum!=0)exit(1);
    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
Runtime Error

Test #1:

score: 0
Runtime Error

input:

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

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Runtime Error

Test #21:

score: 0
Runtime Error

input:

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

output:


result:


Subtask #5:

score: 0
Runtime Error

Test #27:

score: 0
Runtime Error

input:

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

output:


result:


Subtask #6:

score: 0
Runtime Error

Test #34:

score: 0
Runtime Error

input:

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

output:


result:


Subtask #7:

score: 0
Skipped

Dependency #1:

0%