QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#210355#4839. Smaller LCA275307894aAC ✓571ms126344kbC++142.2kb2023-10-11 11:45:362023-10-11 11:45:36

Judging History

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

  • [2023-10-11 11:45:36]
  • 评测
  • 测评结果:AC
  • 用时:571ms
  • 内存:126344kb
  • [2023-10-11 11:45:36]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=4e5+5,M=N*4,K=600+5,mod=998244353,Mod=mod-1;const db eps=1e-6;const int INF=1e9+7;mt19937 rnd(263082);
int n;ll ans[N];
vector<int> S[N];
int Si[N],Sn[N],d[N],fa[N],Tp[N];
void dfs1(int x,int La){
	Si[x]=1;d[x]=d[La]+1;fa[x]=La;
	for(int i:S[x]) if(i^La) dfs1(i,x),Si[x]+=Si[i],Si[Sn[x]]<Si[i]&&(Sn[x]=i);
}
void dfs2(int x,int La){
	Tp[x]=La;if(!Sn[x]) return;dfs2(Sn[x],La);for(int i:S[x]) if(i^fa[x]&&i^Sn[x]) dfs2(i,i);
}
int LCA(int x,int y){
	while(Tp[x]^Tp[y]) d[Tp[x]]<d[Tp[y]]&&(swap(x,y),0),x=fa[Tp[x]];
	return d[x]<d[y]?x:y;
}
int Jp(int x,int y){
	while(d[fa[Tp[y]]]>d[x]) y=fa[Tp[y]];
	return Tp[x]^Tp[y]?Tp[y]:Sn[x];
}
namespace BIT{
	int f[N];void add(int x,int y){while(x<=n) f[x]+=y,x+=x&-x;}
	int qry(int x){int ans=0;while(x) ans+=f[x],x-=x&-x;return ans;}
}
vector<pii> Q[N];
void dfs(int x,int La){
	for(auto i:Q[x]) BIT::add(i.fi,i.se);
	for(int i:S[x]) if(i^La){
		int w=BIT::qry(x);dfs(i,x);w=BIT::qry(x)-w;
		ans[x]+=w;ans[i]-=w;
	}
}
void make(int x,int La){
	for(int i:S[x]) if(i^La) ans[i]+=ans[x],make(i,x);
}
void Solve(){
	int i,j;scanf("%d",&n);
	for(i=1;i<n;i++) {int x,y;scanf("%d%d",&x,&y);S[x].emplace_back(y);S[y].emplace_back(x);}
	dfs1(1,0);dfs2(1,1);
	for(i=1;i<=n;i++) {
		for(j=i+1;1ll*i*j<n;j++){
			int w=i*j+1,Ls=LCA(i,j),px=(i^Ls?Jp(Ls,i):0),py=(j^Ls?Jp(Ls,j):0);//cerr<<i<<' '<<j<<' '<<Ls<<'\n';
			if(Ls>=w){
				ans[1]++;ans[px]--;ans[py]--;
			}
			if(i^Ls) Q[i].emplace_back(w,1),Q[px].emplace_back(w,-1);
			if(j^Ls) Q[j].emplace_back(w,1),Q[py].emplace_back(w,-1);
		}
	}
	dfs(1,0);make(1,0);
	for(i=1;i<=n;i++) printf("%lld\n",1ll*n*(n+1)/2-ans[i]);
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 29996kb

input:

5
1 2
4 2
2 5
3 5

output:

15
15
15
15
14

result:

ok 5 number(s): "15 15 15 15 14"

Test #2:

score: 0
Accepted
time: 541ms
memory: 116844kb

input:

300000
40632 143306
32259 40632
225153 143306
269774 225153
289668 40632
191636 269774
85717 191636
58564 191636
156509 143306
289939 40632
247103 269774
40257 40632
98149 289668
142277 143306
291616 40257
46813 225153
56324 143306
277154 142277
53903 289668
114266 32259
152231 58564
241151 152231
4...

output:

44999437117
44999604051
44999615557
44999614574
44999052534
44999484860
44999371316
44999125588
44999026878
44999118903
44999600090
44999126307
44999249359
44999307961
44999422135
44999360213
44999109672
44999283107
44999293969
44999113471
44999549862
44999278828
44999353626
44999122409
44999352565
...

result:

ok 300000 numbers

Test #3:

score: 0
Accepted
time: 564ms
memory: 119504kb

input:

299999
97687 248627
80337 97687
77032 80337
92616 80337
106631 248627
248726 77032
176093 92616
73262 248726
233147 80337
39942 248726
15921 176093
188366 248627
31058 80337
239076 73262
44766 233147
10344 176093
192127 233147
109285 80337
6814 176093
239926 97687
204083 77032
252211 15921
5158 7703...

output:

44999344660
44999363522
44999206495
44999093451
44999362732
44999276207
44999352410
44999343961
44999149170
44999277616
44999158043
44999332131
44999288440
44999317886
44999301651
44999266803
44999346932
44999241092
44999298075
44999129430
44999277318
44999272323
44999209973
44999271917
44999269931
...

result:

ok 299999 numbers

Test #4:

score: 0
Accepted
time: 571ms
memory: 117608kb

input:

300000
282498 119808
46316 119808
58818 119808
179940 119808
6601 282498
16229 46316
25007 58818
180795 16229
83945 179940
246574 179940
268478 179940
134193 246574
164637 6601
78275 83945
241804 119808
177735 6601
225133 134193
188943 179940
36121 188943
148019 164637
223449 180795
41835 188943
237...

output:

44999540514
44999412634
44999309802
44999471134
44999211366
44999458009
44999479974
44999281366
44999372403
44999448719
44999365824
44999443217
44999455734
44999482977
44999585712
44999540082
44999475151
44999453573
44999399100
44999346705
44999372230
44999256996
44999368064
44999452600
44999473178
...

result:

ok 300000 numbers

Test #5:

score: 0
Accepted
time: 534ms
memory: 116516kb

input:

299999
173205 142232
104374 142232
39513 104374
67867 104374
42519 173205
145713 39513
190264 104374
240190 67867
220708 240190
237545 67867
211015 220708
73889 39513
126319 220708
38274 67867
257538 240190
260471 237545
44453 142232
24527 142232
23487 173205
174569 173205
158023 173205
100347 42519...

output:

44999145790
44999091319
44999049858
44999174810
44998980768
44999252786
44999144473
44998983973
44998953014
44999259775
44998949495
44999055625
44998909201
44998956878
44999261370
44998927703
44999167393
44999140464
44998905939
44998940216
44998919447
44999239170
44999100182
44998941726
44999273329
...

result:

ok 299999 numbers

Test #6:

score: 0
Accepted
time: 562ms
memory: 115780kb

input:

299999
144140 64463
84381 64463
275996 144140
144612 144140
22940 275996
97432 275996
258170 64463
268975 84381
113121 268975
74024 258170
162810 275996
222898 74024
218308 22940
294515 64463
4344 218308
287764 74024
73585 97432
116481 287764
204008 144140
125526 73585
133816 294515
31053 258170
107...

output:

44999005167
44999209294
44998941343
44998935023
44999171993
44999086771
44999206524
44999091272
44998923732
44999092407
44999090745
44998910337
44998836857
44999087877
44999105320
44998879519
44998983003
44998798532
44998760921
44999084330
44999064280
44999054760
44999103030
44999130090
44999053488
...

result:

ok 299999 numbers

Test #7:

score: 0
Accepted
time: 461ms
memory: 119328kb

input:

300000
17050 75638
59628 17050
250487 75638
222372 17050
83877 75638
252612 59628
223823 83877
71675 252612
264309 223823
56862 222372
250608 83877
112630 223823
122103 250608
148130 56862
32428 112630
181607 56862
230036 148130
99321 230036
211188 181607
272235 148130
57324 272235
260876 272235
191...

output:

44999618044
44999147094
44999677093
44999732634
44999460409
44999160790
44999579139
44999467908
44999184681
44999199263
44999231239
44999488195
44999805266
44999547232
44999707240
44999537930
44999505219
44999563833
44999465777
44999426341
44999557653
44999794024
44999548625
44999794023
44999570124
...

result:

ok 300000 numbers

Test #8:

score: 0
Accepted
time: 475ms
memory: 119072kb

input:

299999
221069 282534
214173 282534
24237 221069
204787 282534
245620 204787
136288 221069
209773 245620
287963 245620
292336 24237
21383 292336
172534 209773
127524 209773
16214 21383
87226 287963
170040 172534
103312 87226
52385 127524
140929 170040
193496 52385
203825 87226
115524 170040
220799 52...

output:

44999572210
44999458670
44998911277
44999184039
44999206776
44999443592
44999417299
44999356502
44999179829
44999237265
44999572056
44999206883
44998942302
44999260955
44998835660
44999452577
44999346141
44999194483
44999380831
44998863337
44998893184
44999520307
44999572157
44999173592
44999110483
...

result:

ok 299999 numbers

Test #9:

score: 0
Accepted
time: 444ms
memory: 119748kb

input:

300000
8889 36706
157543 8889
104012 8889
62314 157543
242859 36706
149378 8889
10456 157543
29565 104012
131101 149378
22513 131101
90461 22513
40078 131101
141748 10456
72882 22513
176272 22513
90154 141748
215195 90154
43336 40078
296478 90154
128801 90154
149034 128801
102954 149034
254677 29647...

output:

44999724123
44999887080
44999879556
44999518077
44999609913
44999556275
44999588000
44999593838
44999680913
44999380889
44999880288
44999657021
44999383706
44999144202
44999478288
44999199032
44999614075
44999790343
44999766790
44999445094
44999424718
44999260077
44999887302
44999847443
44999676358
...

result:

ok 300000 numbers

Test #10:

score: 0
Accepted
time: 485ms
memory: 122776kb

input:

299998
29430 279377
87865 279377
33400 87865
149559 33400
218448 149559
274422 87865
62550 149559
215553 274422
239913 274422
107224 149559
289982 218448
256498 239913
143232 239913
103543 289982
90558 107224
254844 143232
7345 90558
139410 143232
171957 90558
85463 139410
207261 171957
128676 13941...

output:

44998919397
44998530568
44998745272
44999059683
44999013065
44999181214
44999129502
44999154742
44999172744
44998691167
44998858765
44999070146
44998807013
44998859372
44998761740
44999120708
44998877194
44998808804
44998912953
44998550644
44999009720
44998818725
44999061235
44998695918
44999085009
...

result:

ok 299998 numbers

Test #11:

score: 0
Accepted
time: 499ms
memory: 125820kb

input:

299999
279808 219366
64566 279808
294679 64566
192527 294679
290866 294679
282142 64566
112420 290866
29858 290866
269073 112420
19694 112420
66844 19694
42940 112420
142231 112420
58837 142231
295419 58837
9002 19694
4808 142231
7272 9002
30675 4808
62872 30675
81916 7272
260542 62872
146224 62872
...

output:

44999374155
44999307472
44999179996
44999188269
44999102614
44999300805
44998993219
44999018542
44999252456
44999480338
44999203231
44998930625
44999347959
44999487732
44999529114
44998903631
44999333440
44999238520
44999388913
44999277968
44999288307
44998958543
44999163087
44999009462
44999226099
...

result:

ok 299999 numbers

Test #12:

score: 0
Accepted
time: 332ms
memory: 118820kb

input:

299998
150616 76335
88273 150616
206635 76335
200072 206635
38950 150616
298642 206635
179779 200072
246700 38950
231698 88273
202098 76335
105468 38950
265562 38950
173901 38950
211307 200072
159253 88273
131738 150616
17278 76335
103492 76335
173877 206635
10117 38950
294264 38950
9644 206635
2619...

output:

44998690423
44998587106
44998552667
44998705776
44998783481
44998918153
44998838542
44998686949
44998913912
44998683184
44998681815
44998501008
44998499683
44998508345
44998507393
44998496703
44998505823
44998505170
44998676050
44998909247
44998770030
44998834748
44998674671
44998908611
44998502057
...

result:

ok 299998 numbers

Test #13:

score: 0
Accepted
time: 350ms
memory: 122788kb

input:

300000
62153 119940
226708 62153
55561 62153
97490 119940
267543 62153
151359 62153
208097 226708
34037 62153
221025 267543
49672 55561
105826 97490
190961 119940
150215 62153
131328 97490
181843 62153
21558 62153
131191 226708
286431 267543
272999 97490
82627 62153
71629 97490
223118 97490
173750 9...

output:

44999490977
44999581101
44999339839
44999579162
44999545119
44999703946
44999296656
44999292608
44999534458
44999700242
44999532035
44999699316
44999698959
44999403875
44999688337
44999688078
44999528187
44999560206
44999276201
44999697464
44999526843
44999526583
44999526346
44999686783
44999273338
...

result:

ok 300000 numbers

Test #14:

score: 0
Accepted
time: 360ms
memory: 121020kb

input:

299998
135922 237786
295644 135922
262303 295644
265807 237786
212115 265807
113095 262303
228408 265807
25124 295644
228236 262303
257454 262303
211200 265807
259284 262303
102582 237786
214954 237786
53868 262303
243618 212115
278431 262303
190297 135922
79400 212115
10680 295644
207199 135922
198...

output:

44998307177
44998533670
44998511017
44998187410
44998492894
44998122262
44998161933
44998111332
44998070905
44998049505
44998478066
44998141914
44998042682
44998139389
44998096031
44998038418
44998057006
44998056138
44998055360
44998091660
44998054028
44998090467
44998133460
44998032259
44998052003
...

result:

ok 299998 numbers

Test #15:

score: 0
Accepted
time: 338ms
memory: 123356kb

input:

299999
150553 278809
170492 150553
229941 150553
241638 278809
84806 170492
24747 241638
171095 84806
244435 278809
158820 229941
120598 229941
217325 229941
202400 170492
62375 278809
239168 84806
119263 84806
107931 170492
281318 241638
17724 278809
5221 84806
25640 84806
174770 278809
227149 2416...

output:

44998747754
44998741449
44998703125
44998566526
44998672467
44998664802
44998786139
44998655221
44998830891
44998778833
44998827849
44998887345
44998825743
44998642903
44998824199
44998521219
44998771812
44998822527
44998518834
44998429416
44998821332
44998428149
44998427598
44998883811
44998635676
...

result:

ok 299999 numbers

Test #16:

score: 0
Accepted
time: 342ms
memory: 118936kb

input:

300000
268282 130589
137710 130589
93460 137710
230491 130589
225183 137710
212453 268282
207913 130589
87858 130589
216796 93460
279662 230491
72760 225183
143429 268282
37775 130589
66916 130589
298071 268282
91115 225183
131823 268282
156244 137710
900 93460
109398 230491
242948 230491
79191 2682...

output:

44999281735
44999366146
44999197401
44999108867
44999371737
44999368622
44999154509
44999109189
44999147361
44999291460
44999100043
44999289165
44999288283
44999067708
44999066611
44999092421
44999358543
44999064050
44999089774
44999062769
44999357496
44999357294
44999132131
44999283427
44999060464
...

result:

ok 300000 numbers

Test #17:

score: 0
Accepted
time: 391ms
memory: 123272kb

input:

299999
143120 236256
148524 236256
200355 236256
36612 143120
266835 236256
238942 236256
96320 148524
289074 236256
141286 236256
194154 143120
198985 148524
5485 236256
186492 236256
151237 148524
150634 236256
284380 236256
249188 143120
141549 236256
205557 148524
288282 143120
106319 236256
112...

output:

44999014097
44999153762
44998915081
44999377507
44999364176
44998890327
44999111383
44998822358
44998820371
44998646022
44998879076
44998816395
44999247378
44998655581
44998814010
44998653471
44999364533
44999028363
44998873391
44998811624
44998811284
44998948277
44998810691
44998871762
44998810193
...

result:

ok 299999 numbers

Test #18:

score: 0
Accepted
time: 396ms
memory: 118340kb

input:

299998
118462 77330
106795 118462
153182 106795
26555 106795
23658 106795
157357 106795
11915 118462
203374 106795
168323 118462
106742 77330
171860 118462
227212 118462
75338 106795
110268 77330
124506 106795
253862 118462
150397 77330
98003 77330
215024 118462
260493 118462
283012 118462
179091 11...

output:

44999331297
44999273639
44999331468
44999047606
44999037182
44999050031
44999189112
44999000737
44998999092
44998587594
44999015801
44998995801
44999051726
44999023452
44999016873
44998993333
44999022106
44999050074
44999131221
44999049644
44999049460
44999119707
44999333219
44999020273
44999129496
...

result:

ok 299998 numbers

Test #19:

score: 0
Accepted
time: 399ms
memory: 122792kb

input:

300000
7713 268697
109798 7713
214823 7713
209700 109798
198009 268697
90616 109798
248974 109798
217891 109798
2919 268697
289625 7713
230098 7713
38379 109798
82546 7713
143115 109798
238446 109798
258032 109798
134218 109798
279009 7713
91097 7713
274170 268697
112624 7713
172812 7713
176525 7713...

output:

44999143485
44999709847
44998964354
44999552973
44999594095
44999707455
44999593654
44999564285
44998904644
44999444525
44999564037
44999442695
44999441991
44999593103
44999440865
44999440408
44999440004
44999434747
44999592958
44999522317
44999438774
44998887002
44999289657
44999656610
44999328462
...

result:

ok 300000 numbers

Test #20:

score: 0
Accepted
time: 369ms
memory: 126344kb

input:

299999
220744 130620
175965 130620
36292 175965
235084 220744
142692 130620
211978 130620
159885 175965
97554 130620
253362 220744
30758 175965
237264 175965
295575 130620
130534 220744
88884 130620
93151 175965
122607 130620
171318 220744
169736 220744
229323 220744
162185 175965
88905 175965
24759...

output:

44998896158
44998942515
44998990095
44998898524
44998719563
44998918962
44998706949
44999302922
44998961069
44998697489
44999278192
44998869196
44998899846
44999358456
44998866263
44998954719
44999278132
44999225071
44999358660
44998953086
44998862912
44999268921
44999127378
44998901444
44998951780
...

result:

ok 299999 numbers

Test #21:

score: 0
Accepted
time: 381ms
memory: 123252kb

input:

300000
146946 294933
286134 294933
87613 294933
252628 146946
98021 286134
235659 294933
2000 286134
4199 286134
155709 294933
57448 294933
254917 286134
235643 146946
123086 286134
127752 294933
173711 146946
30513 286134
12191 294933
120701 286134
77529 286134
290568 294933
263323 146946
200178 28...

output:

44999394841
44998955621
44998919210
44999403875
44999667250
44999060816
44999676964
44999393640
44999679758
44999262590
44999614395
44999348297
44999182207
44998844271
44999257692
44998841716
44998840664
44999680206
44998823677
44999424339
44999254893
44998821561
44998836273
44998820443
44998819952
...

result:

ok 300000 numbers

Test #22:

score: 0
Accepted
time: 3ms
memory: 28220kb

input:

1

output:

1

result:

ok 1 number(s): "1"

Test #23:

score: 0
Accepted
time: 0ms
memory: 30180kb

input:

2
1 2

output:

3
3

result:

ok 2 number(s): "3 3"

Test #24:

score: 0
Accepted
time: 0ms
memory: 31376kb

input:

3
1 2
2 3

output:

6
6
6

result:

ok 3 number(s): "6 6 6"