QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#714998 | #9492. 树上简单求和 | NKheyuxiang | 0 | 3211ms | 87020kb | C++14 | 3.2kb | 2024-11-06 09:48:16 | 2024-11-06 09:48:18 |
Judging History
answer
#include<bits/stdc++.h>
#define N 400005
#define fi first
#define se second
#define mp make_pair
using namespace std;
int n,m;
unsigned long long a[N],val[N];
struct tree{
int h[N],to[N],nxt[N],cnt;
void jb(int u,int v){
to[++cnt]=v;
nxt[cnt]=h[u];
h[u]=cnt;
}
int id[N],pl[N],pr[N],tot;
int up[N][19],dep[N];
void dfs(int u,int fa){
val[u]=a[u]+val[fa];
id[tot]=u;
pl[u]=tot;
++tot;
dep[u]=dep[fa]+1;
up[u][0]=fa;
for(int i=1;i<=17;i++)
up[u][i]=up[up[u][i-1]][i-1];
for(int i=h[u];i!=0;i=nxt[i])
if(to[i]!=fa) dfs(to[i],u);
id[tot]=u;
pr[u]=tot;
tot++;
}
int lca(int x,int y){
if(dep[x]>dep[y]) swap(x,y);
for(int i=17;i>=0;i--)
if(dep[up[y][i]]>=dep[x]) y=up[y][i];
if(x==y) return x;
for(int i=17;i>=0;i--)
if(up[x][i]!=up[y][i])
x=up[x][i],y=up[y][i];
return up[x][0];
}
void work(){
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
jb(x,y);
jb(y,x);
}
dfs(1,0);
}
}T1,T2;
const int t=640;
unsigned long long k[N],ans[N];
pair<int ,int > qt1[N][2],qt2[N][2];
int pre[N];
void init(int l,int r){
for(int i=0;i<=2*n;i++) pre[i]=0;
for(int i=l;i<=r;i++){
int u=T2.id[i],f=(T2.pl[u]==i?1:-1);
pre[T1.pl[u]+1]+=f;
pre[T1.pr[u]+1]-=f;
}
for(int i=1;i<=2*n;i++) pre[i]+=pre[i-1];
}
unsigned long long s0[N],s1[N];
void add(pair<int ,int > p,unsigned long long ad){
int idl=max(0,p.fi-1)/t+1,idr=(p.se+1)/t-1;
if(idl>idr){
for(int i=p.fi;i<=p.se;i++) s0[i]+=ad;
}
else{
for(int i=p.fi;i<idl*t;i++) s0[i]+=ad;
for(int i=idr*t+t;i<=p.se;i++) s0[i]+=ad;
for(int i=idl;i<=idr;i++) s1[i]+=ad;
}
}
unsigned long long qry(pair<int ,int > p){
int idl=max(0,p.fi-1)/t+1,idr=(p.se+1)/t-1;
unsigned long long res=0;
if(idl>idr){
for(int i=p.fi;i<=p.se;i++){
int u=T2.id[i];
unsigned long long w=s0[T1.pl[u]]+s1[T1.pl[u]/t]-s0[T1.pr[u]]-s1[T1.pr[u]/t];
if(T2.pl[u]==i) res+=w;
else res-=w;
}
}
else{
for(int i=p.fi;i<idl*t;i++){
int u=T2.id[i];
unsigned long long w=s0[T1.pl[u]]+s1[T1.pl[u]/t]-s0[T1.pr[u]]-s1[T1.pr[u]/t];
if(T2.pl[u]==i) res+=w;
else res-=w;
}
for(int i=idr*t+t;i<=p.se;i++){
int u=T2.id[i];
unsigned long long w=s0[T1.pl[u]]+s1[T1.pl[u]/t]-s0[T1.pr[u]]-s1[T1.pr[u]/t];
if(T2.pl[u]==i) res+=w;
else res-=w;
}
}
return res;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%llu",&a[i]);
T1.work();
T2.work();
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d%llu",&x,&y,&k[i]);
int lc1=T1.lca(x,y);
int lc2=T2.lca(x,y);
qt1[i][0]=mp(T1.pl[lc1]+1,T1.pl[x]);
qt1[i][1]=mp(T1.pl[lc1],T1.pl[y]);
qt2[i][0]=mp(T2.pl[lc2]+1,T2.pl[x]);
qt2[i][1]=mp(T2.pl[lc2],T2.pl[y]);
add(qt1[i][0],k[i]);
add(qt1[i][1],k[i]);
ans[i]=val[x]+val[y]-val[lc2]*2+a[lc2]+qry(qt2[i][0])+qry(qt2[i][1]);
}
for(int i=0;i*t<n*2;i++){
int l=i*t,r=min(n*2-1,i*t+t-1);
init(l,r);
unsigned long long sum=0;
for(int j=1;j<=m;j++){
sum+=k[j]*(pre[qt1[j][0].se+1]-pre[qt1[j][0].fi]+pre[qt1[j][1].se+1]-pre[qt1[j][1].fi]);
if(qt2[j][0].fi<=l&&r<=qt2[j][0].se) ans[j]+=sum;
if(qt2[j][1].fi<=l&&r<=qt2[j][1].se) ans[j]+=sum;
}
}
for(int i=1;i<=m;i++) printf("%llu\n",ans[i]);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 17ms
memory: 30892kb
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:
wrong answer 2958th lines differ - expected: '11181711081335800450', found: '17600918342177019288'
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: 14
Accepted
time: 2999ms
memory: 83412kb
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:
ok 200000 lines
Test #22:
score: 14
Accepted
time: 3211ms
memory: 79100kb
input:
200000 200000 13175752638648662841 17926176333479943540 18069418271192836667 7662981418770774166 17432280672869071045 9361466030141569604 17336291298429915451 758279154724011577 10229986883918215412 16695796270233481895 1104033984864960726 9768530369533627193 7121962912997584423 8574667967472399164 ...
output:
761007177180158471 99932139211644879 9085452500188024811 10579196290428182519 9823187704909577710 18023302821814112676 12490017484705421441 12628966555486388857 14265121989865566834 6520346880672680237 13101459183526308131 999924043939340162 18263995506773932901 5204528109864295202 12531805215875429...
result:
ok 200000 lines
Test #23:
score: 0
Wrong Answer
time: 2938ms
memory: 85712kb
input:
200000 200000 7686280868723494190 956703982700755675 9999621735507690021 16173863373498393354 13710049849600478540 17103229081434028663 17565545023679367555 2828484246894512005 1583487132574088302 6282276626784421099 11842426946394217784 3255349046251970557 9837219010639574935 8803965402777990679 10...
output:
9027980728293426417 390552393210324231 11163738403290403569 7251051512011369232 11710945043516484177 8385783841330898676 10540689232459717148 13494924758898800208 10783463309429788767 15497109458285729613 3973164643641949159 16591368938886703497 17545967451093599325 7502098747509618204 7748818626114...
result:
wrong answer 17135th lines differ - expected: '1780309334734624428', found: '13195491803937756582'
Subtask #5:
score: 0
Wrong Answer
Test #27:
score: 0
Wrong Answer
time: 2812ms
memory: 87020kb
input:
200000 200000 1958469220619413759 14991498002015735322 6054491201406941902 18206143187746582567 15082377615826460430 2936248617457291604 10073577150351675920 16534472678586906457 2207599132486246393 10301540360769075442 1492580560381080472 551692353431379140 13238280352539145808 8462626987240986565 ...
output:
5934714582025602017 7612644482907856514 7664363696211351499 10419050713553268082 17029715834498158241 17333405773874432711 6463538357881530326 7781748456633366931 17312050420753525411 9085204958069193709 15237835478514966949 1011923303415334401 15280591493481885526 11613220426756932450 3224741020426...
result:
wrong answer 1st lines differ - expected: '11479812171669345085', found: '5934714582025602017'
Subtask #6:
score: 0
Wrong Answer
Test #34:
score: 0
Wrong Answer
time: 1576ms
memory: 85848kb
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:
wrong answer 68423rd lines differ - expected: '16492830305915339405', found: '7083947704320693650'
Subtask #7:
score: 0
Skipped
Dependency #1:
0%