QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#402628#3847. Airlinekevinyang#AC ✓2810ms305348kbC++172.3kb2024-05-01 04:50:392024-05-01 04:50:40

Judging History

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

  • [2024-05-01 04:50:40]
  • 评测
  • 测评结果:AC
  • 用时:2810ms
  • 内存:305348kb
  • [2024-05-01 04:50:39]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
int mxn = 1000005;
vector<vector<int>>adj(mxn); int ln = 21;
vector<vector<int>>dp(mxn,vector<int>(ln));
vector<int>lvl(mxn);
vector<int>sz(mxn);
void dfs(int u, int p){
	lvl[u] = lvl[p]+1;
	dp[u][0] = p;
	sz[u] = 1;
	for(int i = 1; i<ln; i++){
		dp[u][i] = dp[dp[u][i-1]][i-1];
	}
	for(int nxt: adj[u]){
		if(nxt==p)continue;
		dfs(nxt,u);
		sz[u]+=sz[nxt];
	}
}
int lca(int x, int y){
	if(lvl[x]<lvl[y])swap(x,y);
	int dif = lvl[x]-lvl[y];
	for(int i = 0; i<ln; i++){
		if((1<<i)&dif){
			x = dp[x][i];
		}
	}
	if(x==y)return x;
	for(int i = ln-1; i>=0; i--){
		if(dp[x][i]!=dp[y][i]){
			x = dp[x][i]; y = dp[y][i];
		}
	}
	return dp[x][0];
}
int dist(int x, int y){
	int u = lca(x,y);
	return lvl[x]+lvl[y]-2*lvl[u];
}
signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int n,q;
	cin >> n >> q;
	for(int i = 0; i<n-1; i++){
		int x,y;
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	dfs(1,0);
	while(q--){
		int x,y;
		cin >> x >> y;
		vector<int>path;
		vector<int>path2;
		int u = lca(x,y);
		while(x!=u){
			path.push_back(x);
			x = dp[x][0];
		}
		while(y!=u){
			path2.push_back(y);
			y = dp[y][0];
		}
		path.push_back(u);
		reverse(path2.begin(),path2.end());
		for(int nxt: path2){
			path.push_back(nxt);
		}
		int len = path.size();
		vector<int>cnt(len);
		vector<int>pre(len);
		vector<int>suf(len);
		for(int i = 0; i<len; i++){
			if(path[i] == u){
				int tot = n;
				if(i>0){
					tot-=sz[path[i-1]];
				}
				if(i+1<len){
					tot-=sz[path[i+1]];
				}
				cnt[i] = tot;
			}
			else if(i>0 && dp[path[i-1]][0] == path[i]){
				cnt[i] = sz[path[i]] - sz[path[i-1]];
			}
			else if(i+1<len && dp[path[i+1]][0] == path[i]){
				cnt[i] = sz[path[i]] - sz[path[i+1]];
			}
			else{
				cnt[i] = sz[path[i]];
			}
			pre[i] = suf[i] = cnt[i];
		}
		for(int i = 1; i<len; i++){
			pre[i] += pre[i-1];
		}
		for(int i = len-2; i>=0; i--){
			suf[i] += suf[i+1];
		}
		int rq = len/2+1;
		int ans = 0;
		for(int i = 0; i<len; i++){
			if(i+rq < len){
				ans+=cnt[i]*suf[i+rq];
			}
			if(i-rq >= 0){
				ans+=cnt[i] * pre[i-rq];
			}
		}
		cout << ans/2 << '\n';
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 92ms
memory: 237360kb

input:

1000 100000
552 9
456 720
540 790
628 695
848 478
66 268
798 360
773 277
116 471
874 792
912 784
502 831
359 965
925 434
677 629
271 670
76 755
92 200
814 422
922 266
617 44
480 331
18 662
153 753
669 491
368 187
99 867
476 808
774 509
98 147
724 478
447 182
923 469
881 665
674 589
770 613
436 310
8...

output:

8905
976
2924
5646
3837
5966
5530
2221
2394
2570
2238
4823
4034
2458
2582
1259
4751
2694
456
1380
3199
5788
2214
3854
3098
4086
5734
4148
3065
3428
3937
4461
2845
5935
5122
5625
2614
704
6312
3180
2480
7481
9410
4642
1660
4875
5767
2976
5717
5766
4783
4553
2483
3635
4125
4093
6074
8675
3988
4695
313...

result:

ok 100000 lines

Test #2:

score: 0
Accepted
time: 121ms
memory: 237848kb

input:

9392 100000
4521 1973
362 7795
6505 6798
6079 8431
5691 9228
774 4060
2800 6246
6995 4890
5981 7196
6747 6781
8642 1970
4609 7891
6692 3764
1918 8164
8889 4386
6997 2266
8080 2062
1474 2612
5128 1618
6763 604
6611 4768
9265 2462
9323 9067
4086 7292
7661 5091
19 8937
3209 5829
4079 6058
1912 4137
443...

output:

25865
20795
47691
36294
117742
45172
57330
89573
117973
132250
35330
292130
28222
23630
79047
38816
217653
54722
121448
46997
75338
16394
24369
137591
17869
186807
34649
20072
15377
82113
24090
260999
67202
15795
51210
24248
33377
18702
163416
58397
29846
104190
78268
21985
58729
60089
77200
27965
8...

result:

ok 100000 lines

Test #3:

score: 0
Accepted
time: 123ms
memory: 237740kb

input:

10000 100000
9893 2063
2863 2642
8661 4723
6164 9513
6820 6207
4488 2221
1325 5718
1556 7921
5625 8519
6390 5649
418 8063
6480 8380
7514 2373
9617 726
1487 6460
2513 2370
6802 7614
2530 2877
4146 7723
2545 9741
2921 4690
7311 6782
7396 3695
9619 6495
4591 1657
935 9454
6828 4754
3923 9077
725 8709
4...

output:

301945
54742
255647
42833
42190
115868
126805
72842
58873
37057
117958
75501
36147
52590
56534
48946
45216
179027
51981
54150
34061
94817
83797
72851
130990
160292
30221
81990
111442
26773
73980
38218
70294
303262
52096
204388
26876
216714
73098
230567
180645
96737
124516
25837
103832
27278
37849
93...

result:

ok 100000 lines

Test #4:

score: 0
Accepted
time: 215ms
memory: 241200kb

input:

98549 100000
82689 70448
77356 39505
7527 5072
89160 36614
1539 37083
3256 15723
91761 73823
9152 52058
79202 73747
47554 40484
3207 62832
96291 76455
85804 74263
75592 40690
16876 90408
48161 77604
73371 80844
40649 70129
87295 60940
65605 26715
32778 50672
40569 69825
13624 47206
15834 81212
62890...

output:

2268380
926599
2183002
1702915
836581
177673
1413412
918753
6124931
4566130
1089211
9862469
1721224
2320780
601961
574275
7243947
1626922
130095
3762731
583708
2859944
306238
1100329
1124119
773908
8423096
1233858
1789556
2075624
3582238
3224532
10322578
606003
575441
1432311
1752507
1493374
225848
...

result:

ok 100000 lines

Test #5:

score: 0
Accepted
time: 211ms
memory: 241144kb

input:

100000 100000
6485 28819
91949 30150
52641 17533
10545 52999
42821 43631
52176 83277
66684 9548
29337 74462
90920 25011
47466 13053
83527 7709
12707 25795
90508 82266
46872 57123
60150 97514
76184 41073
73305 90274
51117 72775
21957 89242
21849 96322
59134 86949
15879 40843
71163 17671
99618 96690
9...

output:

200430
4076423
813976
6802322
3547614
3149979
5727130
2110580
3217987
217799
1416755
1046962
1097030
351235
810715
367530
162075
934424
461963
3098238
773882
1336893
3309131
717298
1717283
193899
116706
5542089
380797
1296714
1323500
2692618
447799
701192
116204
622110
236020
1279977
297384
547912
2...

result:

ok 100000 lines

Test #6:

score: 0
Accepted
time: 923ms
memory: 273940kb

input:

971873 100000
436749 616077
202840 410896
455619 967072
103439 822434
475653 398112
461031 486647
343026 341908
861220 641003
796134 726337
481939 80955
727467 87328
439111 929971
614634 944496
593211 114711
119419 855657
201230 264491
210286 147802
32084 285406
718264 254462
390417 57890
684402 868...

output:

151895839
5567962
2048780
7755912
3298118
291200668
2026946
3803072
10195185
25852053
8564427
37758355
4632161
3646199
10536917
31895919
41481500
16188147
10264801
5882102
20896091
5441699
48493636
8893505
44641595
51487773
25764094
32152214
4989029
10363357
8539733
15998581
44503767
10306841
307950...

result:

ok 100000 lines

Test #7:

score: 0
Accepted
time: 948ms
memory: 274996kb

input:

1000000 100000
803384 460095
915180 745831
32349 23515
580947 448659
188631 274157
934991 711308
419176 808090
309146 586352
991644 637573
755008 737123
65329 299447
724012 469040
421444 502777
633955 629892
912207 342364
736852 674360
755495 502086
993988 249100
479859 362258
359743 424921
379910 2...

output:

40080441
32130667
38441771
8989143
54574184
34475496
14887507
7644291
6840414
96392883
71876437
61536099
109314471
1835776
65681185
190466381
3115293
5730318
28144459
27307083
4219651
14991979
10338001
4149617
96025528
26892158
4216803
11507748
3715762
38929181
75754148
36061602
16200031
15557529
35...

result:

ok 100000 lines

Test #8:

score: 0
Accepted
time: 661ms
memory: 274548kb

input:

1000000 100000
762104 839878
68400 601674
322741 68400
797458 681633
979286 121964
541137 30448
408270 173352
726998 993520
235077 267868
68400 650976
68400 678723
68400 87880
68400 736923
68400 599313
55248 68400
632321 986186
111629 831883
708807 701035
334748 68400
217493 661224
948145 973190
661...

output:

1000000
13
7
999998
6
1999992
10
33
7
20
6
9
7
999995
999996
3
999998
3
18
9
7
4
3
4
1999993
5
10
1999989
999997
6
999993
6
999995
3
9
8
999999
1000000
1000002
999996
999996
6
999997
999996
999999
2999987
10
999996
999996
2999985
1000001
13
16
999998
14
1000004
7
999998
1999990
7
11
6
5
1000010
9999...

result:

ok 100000 lines

Test #9:

score: 0
Accepted
time: 131ms
memory: 241120kb

input:

100000 100000
48322 67969
48322 28622
86056 48322
48322 54975
48322 71559
48322 74678
48322 61562
55559 57549
72967 48322
48322 74587
53228 99798
3883 55913
51578 45502
76373 71957
73524 28601
53578 48322
48322 68623
3534 96554
48322 11104
66053 24812
33176 33210
23815 53399
90108 48322
93619 48322
...

output:

3
99998
5
8
6
99996
3
99997
3
99998
6
99996
5
199990
7
5
3
4
6
10
199992
99997
7
99998
99998
3
14
8
11
14
19
99997
16
100002
9
6
100003
5
100000
99998
10
38
6
99996
199991
99999
199998
100000
99999
99996
199990
199992
11
4
4
99999
299985
199995
100001
99993
3
99996
100010
199982
99997
7
5
6
100004
1...

result:

ok 100000 lines

Test #10:

score: 0
Accepted
time: 88ms
memory: 237968kb

input:

10000 100000
2332 3313
2381 815
8819 9961
1254 42
4523 2381
5023 2381
2381 5194
2381 3983
2381 4062
7386 2381
370 2381
1658 696
8044 1968
2381 7472
2064 2381
2381 2927
5961 5215
6971 2312
2381 3737
9178 6121
2381 4234
2381 8690
1440 6852
2381 4710
2381 4679
4771 9146
2381 7615
972 9558
7208 1972
102...

output:

9996
9999
6
9998
7
10
5
8
4
5
4
11
7
19992
9998
9
10
3
9998
7
3
19990
9997
10
7
3
9996
5
5
9997
4
6
4
29987
6
4
19984
6
5
5
10
10
9999
9998
3
9996
9998
3
9999
5
5
10006
9999
9998
19991
7
10003
7
3
10000
5
10006
19992
3
9998
8
5
10011
6
14
5
7
10000
4
13
9
3
4
19981
6
11
6
9997
9998
19991
3
5
10004
5...

result:

ok 100000 lines

Test #11:

score: 0
Accepted
time: 2810ms
memory: 305348kb

input:

1000000 89
852360 73132
631358 260153
444669 320143
263042 223480
666864 447948
321887 799867
569356 94440
382836 553144
88681 148334
973288 94060
128162 767754
109735 20622
718347 417824
137685 835786
608403 777858
288343 956521
886633 249613
970032 602109
12614 931831
434033 180430
680042 733142
3...

output:

64688060443
178343647352
122392998305
36864716828
156361879793
98397598018
120032263212
187193623716
121476122571
108923197723
227273407885
215080461636
84247716640
47142901252
82568916191
166722152785
65186761269
89545003980
87630840147
218162363174
70269523657
123840378342
184180925414
14588884914...

result:

ok 89 lines

Test #12:

score: 0
Accepted
time: 806ms
memory: 245368kb

input:

100000 654
14094 65371
64109 32442
54197 75935
76576 33789
84648 95579
60908 81051
84438 24255
77095 71189
40589 34125
26067 31275
60375 81820
49373 11224
93763 63945
35858 98885
77684 32762
56313 2592
50525 47765
31878 69666
58438 94687
43900 76300
64930 65881
3444 79640
44835 35833
3539 46318
7262...

output:

1792654836
664431408
1829104078
1703697910
1514119170
2261006102
1752572876
1887189620
1809251762
2477790208
986199644
1835006134
2295254123
2113815439
1975714246
1790091210
621162359
1461805166
2434299652
1871259687
1765614445
953223742
2022351822
1719233611
1987312050
2450740638
1944826857
2324349...

result:

ok 654 lines

Test #13:

score: 0
Accepted
time: 263ms
memory: 238776kb

input:

10000 6991
6736 5626
3091 1567
5118 5521
8935 6462
3648 7915
9646 9182
2847 6622
993 2063
9575 7582
5653 7296
9990 4807
3368 1523
5943 5146
4842 5591
2837 8798
4036 7979
7878 4387
790 9198
7643 566
3980 2182
5938 8640
3335 7985
4901 8836
7521 901
5531 2118
9758 152
2701 2175
6048 8125
5139 5316
5492...

output:

24358693
21621412
23398875
20932753
18820619
21248958
13989549
20500809
23883614
14783070
21993651
23842748
20359922
17339745
24325143
23369616
17494507
13281549
16182004
19953242
11687401
21807030
16596342
23515829
21237557
4797575
14581960
8611206
19217325
21807581
22616163
24336174
24704748
15293...

result:

ok 6991 lines