QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#714953#9492. 树上简单求和NKheyuxiang0 3411ms88060kbC++143.2kb2024-11-06 09:27:572024-11-06 09:27:58

Judging History

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

  • [2024-11-06 09:27:58]
  • 评测
  • 测评结果:0
  • 用时:3411ms
  • 内存:88060kb
  • [2024-11-06 09:27:57]
  • 提交

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=(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=(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: 8ms
memory: 31152kb

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: 3266ms
memory: 78328kb

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: 3411ms
memory: 78792kb

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: 3189ms
memory: 82732kb

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: 3049ms
memory: 81536kb

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: 1673ms
memory: 88060kb

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%