QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#717724 | #9492. 树上简单求和 | sunrise1024 | 0 | 5032ms | 102540kb | C++14 | 4.3kb | 2024-11-06 18:48:27 | 2024-11-06 18:48:28 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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%