QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#96757#6267. Triples of CowsAFewSuns100 ✓212ms50272kbC++143.2kb2023-04-15 16:05:372023-04-15 16:05:40

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-15 16:05:40]
  • 评测
  • 测评结果:100
  • 用时:212ms
  • 内存:50272kb
  • [2023-04-15 16:05:37]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
namespace my_std{
	#define ll long long
	#define bl bool
	ll my_pow(ll a,ll b,ll mod){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res=(res*a)%mod;
			a=(a*a)%mod;
			b>>=1;
		}
		return res;
	}
	ll qpow(ll a,ll b){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res*=a;
			a*=a;
			b>>=1;
		}
		return res;
	}
	#define db double
	#define pf printf
	#define pc putchar
	#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
	#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
	#define go(u) for(ll i=head[u];i;i=e[i].nxt)
	#define enter pc('\n')
	#define space pc(' ')
	#define fir first
	#define sec second
	#define MP make_pair
	#define il inline
	#define inf 8e18
	#define random(x) rand()*rand()%(x)
	#define inv(a,mod) my_pow((a),(mod-2),(mod))
	il ll read(){
		ll sum=0,f=1;
		char ch=0;
		while(!isdigit(ch)){
			if(ch=='-') f=-1;
			ch=getchar();
		}
		while(isdigit(ch)){
			sum=sum*10+(ch^48);
			ch=getchar();
		}
		return sum*f;
	}
	il void write(ll x){
		if(x<0){
			x=-x;
			pc('-');
		}
		if(x>9) write(x/10);
		pc(x%10+'0');
	}
	il void writeln(ll x){
		write(x);
		enter;
	}
	il void writesp(ll x){
		write(x);
		space;
	}
}
using namespace my_std;
ll n,head[400040],cnt=0,f[400040],d[400040],dep[400040],tg[400040],ans=0;
ll fa[400040],tot[400040],sum[400040],lz[400040],siz[400040],top[400040];
struct node{
	ll nxt,to;
}e[800080];
void add(ll u,ll v){
	e[++cnt].nxt=head[u];
	e[cnt].to=v;
	head[u]=cnt;
}
ll find(ll x){
	if(x==fa[x]) return x;
	ll tmp=find(fa[x]);
	if(fa[x]!=tmp) lz[x]+=lz[fa[x]];
	return fa[x]=tmp;
}
void dfs(ll faa,ll u){
	f[u]=faa;
	dep[u]=dep[faa]+1;
	go(u){
		ll v=e[i].to;
		if(v==faa) continue;
		dfs(u,v);
	}
}
ll calc(ll x){
	find(x);
	return lz[x]+lz[fa[x]];
}
void merge(ll x,ll y){
	x=find(x);
	y=find(y);
	if(siz[x]<siz[y]) swap(x,y);
	fa[y]=x;
	siz[x]+=siz[y];
	if(dep[top[x]]>dep[top[y]]) top[x]=top[y];
	lz[y]-=lz[x];
}
int main(){
	n=read();
	fr(i,1,n-1){
		ll u=read(),v=read();
		d[u]++;
		d[v]++;
		add(u,n+i);
		add(n+i,u);
		add(n+i,v);
		add(v,n+i);
	}
	dfs(0,1);
	fr(i,1,2*n-1) fa[i]=i;
	fr(i,1,2*n-1) siz[i]=1;
	fr(i,1,2*n-1) top[i]=f[i];
	fr(u,n+1,2*n-1){
		tot[u]=2;
		go(u){
			ll v=e[i].to;
			sum[u]+=d[v];
		}
	}
	fr(i,1,n) ans+=d[i]*(d[i]-1);
	fr(u,1,n){
		writeln(ans);
		ll all=0,nsum=0,tp=f[u],oth=0;
		go(u){
			ll v=find(e[i].to);
			all+=tot[v]-1;
			if(dep[tp]>dep[top[v]]) tp=top[v];
		}
		ans-=all*(all-1);
		go(u){
			ll v=find(e[i].to),tmp=all-tot[v]+1,sumv=sum[v];
			if(top[v]){
				sumv+=tg[top[v]];
				if(f[top[v]]) sumv+=calc(f[top[v]]);
			}
			if(top[v]==tp){
				oth=tmp;
				if(top[v]) nsum-=tg[top[v]];
				if(f[top[v]]) nsum-=calc(f[top[v]]);
			}
			nsum+=sumv-all-tot[v]+1;
			nsum+=(tot[v]-1)*tmp;
			ans+=((tmp-1)*(tmp-1)-(tmp-1))*(tot[v]-1);
			ans+=2*(tmp-1)*(sumv-all);
		}
		go(u){
			ll v=find(e[i].to),tmp=all-tot[v]+1;
			lz[v]+=tmp-1;
		}
		go(u) merge(u,e[i].to);
		ll fu=find(u);
		tot[fu]=all;
		sum[fu]=nsum;
		if(top[fu]){
			tg[top[fu]]+=oth-1;
			sum[fu]-=oth-1;
			if(f[top[fu]]) sum[find(f[top[fu]])]+=oth-1;
		}
	}
}

詳細信息

Test #1:

score: 5
Accepted
time: 4ms
memory: 17620kb

input:

3
1 2
2 3

output:

2
0
0

result:

ok 3 lines

Test #2:

score: 5
Accepted
time: 0ms
memory: 17640kb

input:

4
1 2
1 3
1 4

output:

6
6
0
0

result:

ok 4 lines

Test #3:

score: 5
Accepted
time: 5ms
memory: 17620kb

input:

5
3 5
5 1
1 4
1 2

output:

8
10
2
0
0

result:

ok 5 lines

Test #4:

score: 5
Accepted
time: 1ms
memory: 17768kb

input:

500
11 3
327 355
314 180
428 417
349 438
319 16
322 365
430 4
116 384
95 469
476 16
96 444
330 323
282 380
179 365
416 151
361 34
422 417
122 440
206 264
169 381
237 420
167 47
118 421
442 149
474 112
135 359
230 221
178 391
39 464
326 105
198 24
33 419
455 240
120 50
406 134
124 32
186 424
6 157
21...

output:

1970
1960
1958
1956
2050
2046
2044
2042
2040
2038
2034
2032
2028
2026
2022
2020
2076
2080
2090
2074
2066
2058
2056
2054
2058
2048
2046
2048
2046
2044
2042
2040
2052
2050
2082
2070
2068
2108
2106
2102
2100
2106
2104
2110
2108
2106
2120
2126
2122
2134
2166
2162
2130
2122
2120
2114
2106
2102
2100
2094
...

result:

ok 500 lines

Test #5:

score: 5
Accepted
time: 5ms
memory: 17764kb

input:

500
117 273
162 26
468 332
44 21
227 163
368 215
241 403
60 319
297 303
376 139
14 134
438 452
8 65
195 48
230 188
475 485
152 136
35 375
272 487
72 242
208 180
330 157
75 487
278 159
110 497
364 339
255 73
405 16
463 368
26 320
226 377
149 410
240 436
439 56
43 422
37 287
186 228
347 248
294 435
67...

output:

1952
1950
1942
1932
1934
1928
1920
1914
1912
1910
1908
1906
1904
1898
1892
1932
2080
2070
2216
2212
2210
2238
2236
2234
2232
2230
2242
2330
2326
2314
2312
2324
2322
2372
2386
2384
2394
2392
2388
2386
2380
2378
2376
2394
2392
2390
2396
2402
2412
2410
2406
2402
2400
2394
2406
2396
2538
2534
2588
2586
...

result:

ok 500 lines

Test #6:

score: 5
Accepted
time: 2ms
memory: 20140kb

input:

5000
192 2280
866 1993
3318 2270
866 4634
1062 1191
1616 1183
3798 951
866 1590
4607 3400
866 4962
1816 4504
468 325
4569 1736
866 1130
2690 866
4389 866
4240 1120
1932 1614
2487 3373
866 1903
1261 2826
219 1064
44 4360
866 1333
866 1636
2726 2577
2130 866
4693 4818
1190 866
3319 2069
1424 240
1113 ...

output:

4926576
4926574
4926572
4926566
4926564
4926560
4926554
4922120
4922118
4917686
4917684
4917680
4913250
4908822
4908820
4904394
4904356
4904380
4904378
4904376
4904374
4904372
4904370
4899946
4899970
4895548
4895546
4891126
4886708
4886706
4886704
4882288
4877874
4877872
4877870
4877868
4873456
4869...

result:

ok 5000 lines

Test #7:

score: 5
Accepted
time: 2ms
memory: 18212kb

input:

5000
1026 19
4489 1374
1374 976
2917 317
2875 19
3741 2419
3056 444
19 1591
1983 19
4825 1374
2444 1374
2937 19
1374 2301
1246 1374
19 4829
19 3893
1374 3084
19 2482
19 3772
19 2434
4565 2642
3810 3291
1650 4033
1374 3824
4103 3281
19 852
19 2561
1018 112
1374 2096
1661 1374
19 280
19 3695
356 2671
...

output:

7126950
7122520
7118092
7118090
7113664
7113652
7113650
7110676
7107704
7103280
7100310
7095888
7091468
7088500
7084082
7079666
7075252
7070840
7066430
10708504626
10708504624
10708504634
10693938346
10679385276
10664845418
10664842452
10650315800
10650315798
10650315796
10635802344
10635799380
1062...

result:

ok 5000 lines

Test #8:

score: 5
Accepted
time: 1ms
memory: 18212kb

input:

5000
3656 2617
1546 2617
3883 2531
487 302
2617 1655
2617 3150
684 4158
2641 4762
2552 2300
2617 2415
3766 1485
3401 155
2458 2617
1941 1219
2617 4612
990 4670
4551 1784
2617 3315
2617 3058
2617 4611
3379 2555
1745 1914
2617 4652
3820 1368
557 4236
4777 2667
774 4214
4592 961
3468 754
539 3369
2390 ...

output:

5011042
5006584
5006580
5006538
5002082
5002074
4997620
4997618
4997612
4997618
4997616
4993164
4988714
4988712
4988710
4988840
4984392
4984110
4984106
4979660
4975216
4970774
4970770
4970768
4970766
4970762
4966322
4961884
4961904
4957468
4953034
4948602
4948598
4948588
4944158
4939730
4939728
4935...

result:

ok 5000 lines

Test #9:

score: 5
Accepted
time: 1ms
memory: 18164kb

input:

5000
1963 1714
2089 1714
1958 1714
1174 516
2468 1714
4013 780
542 1714
1714 921
1714 494
2799 3447
1714 4167
2663 1377
4753 58
3643 4557
1714 623
1714 2198
4997 1992
1518 722
1714 1367
2723 4870
4103 2072
1714 4384
4299 2533
433 969
1714 4644
1253 1652
4838 2735
1508 1714
596 4817
2465 3850
3287 23...

output:

5108150
5103636
5099124
5099122
5099116
5099086
5099084
5099076
5094566
5094564
5094562
5094560
5094556
5090048
5085542
5081038
5076536
5076532
5076490
5071990
5067492
5067490
5062994
5058500
5054008
5049518
5049516
5049514
5045026
5045066
5045064
5040578
5040626
5036142
5036140
5031658
5027178
5022...

result:

ok 5000 lines

Test #10:

score: 5
Accepted
time: 2ms
memory: 20316kb

input:

5000
1952 4980
1776 4362
3887 1033
1033 4047
523 4980
357 1033
1033 941
4631 1033
1033 3253
960 4980
1033 2582
4980 887
984 2694
3715 4956
4728 1376
4980 3197
2996 4357
1490 1033
1033 2798
9 1033
4980 1084
1033 3349
2554 4980
204 1037
1033 4660
3004 1249
3817 2960
1033 1761
1033 2152
1033 1740
1033 ...

output:

7200814
7197878
7193392
7190458
7190456
7187524
7183040
7178558
7175628
7171148
7168220
7163742
7159266
7154792
7151866
7147394
7147226
7142756
7138288
7133822
7130898
7126434
7126428
7121966
7117506
7113048
7108592
7108598
7105676
7101222
7096770
7092320
7087872
7087870
7087868
7087866
7084946
7080...

result:

ok 5000 lines

Test #11:

score: 5
Accepted
time: 212ms
memory: 49776kb

input:

200000
180343 93112
133794 25463
15259 32390
161405 75514
53906 75514
31334 75514
145757 75514
91720 75514
113316 10952
75514 24136
30812 144626
84587 109632
28810 104546
75514 162784
73000 185642
75514 12153
75514 30841
74493 76012
177125 150153
100571 107545
118366 139210
10965 75514
21955 75514
7...

output:

7907948828
7907771022
7907771020
7907771018
7907771016
7907593212
7907593202
7907593200
7907593198
7907593196
7907593194
7907593192
7907593200
7907593198
7907415396
7907237596
7907059798
7907059582
7907059590
7907059588
7906881792
7906881790
7906703996
7906526204
7906526202
7906348412
7906170624
790...

result:

ok 200000 lines

Test #12:

score: 5
Accepted
time: 169ms
memory: 48692kb

input:

200000
156524 164378
63451 181093
142236 156524
156524 91309
195366 63451
63451 54126
62067 43431
48083 17306
156524 139870
156524 79853
63451 118039
63451 10162
116377 114109
82955 48083
17725 63451
1075 156524
77519 156524
156524 118428
63451 126448
108533 156524
133574 156524
63451 10239
119214 1...

output:

11749107100
11748929116
11748810644
11748774978
11748774704
11748656234
11748537766
11748419300
11748300836
11748300562
11748122580
11747944600
11747826138
11747648160
11747470184
11747292210
11747173750
11746995778
11746817808
11746699350
11746521382
11746343416
11746343414
11746165450
11748102948
...

result:

ok 200000 lines

Test #13:

score: 5
Accepted
time: 169ms
memory: 48780kb

input:

200000
128878 43530
11660 61275
93778 135514
128878 65607
105027 128878
99196 126852
121316 119378
12994 121964
128878 157185
186752 128878
66811 97145
166913 95469
188773 91487
128878 164320
52546 128878
173916 128878
180121 126852
174374 128878
123398 126852
123003 128878
109982 128878
106656 1288...

output:

11440362682
11440184680
11440006680
11439828682
11439650686
11439472692
11439354062
11439176070
11439176068
11439176066
11439057438
11438879448
11438701460
11438523474
11438345490
11438167508
11438167506
11437989526
11437989516
11437811538
11437633562
11437455588
11437455584
11437336958
11437158986
...

result:

ok 200000 lines

Test #14:

score: 5
Accepted
time: 141ms
memory: 49040kb

input:

200000
75292 57657
154653 141350
140800 57657
57657 162746
124811 59959
154653 89884
57657 25957
60896 67370
183207 26852
57657 43172
188291 57657
154653 102124
57657 157547
132684 57657
154653 143124
124811 188592
57657 109286
66896 87163
57657 30111
154653 131248
107225 57657
139132 29848
181221 1...

output:

11764531042
11764353072
11764175104
11763997138
11763878524
11763759912
11763641302
11763634162
11763515554
11763337590
11763159628
11762981668
11762803710
11762685104
11762507148
11762388544
11762353088
11762175134
11761997182
11761878580
11761700630
11761665176
11761487228
11761309282
11761131338
...

result:

ok 200000 lines

Test #15:

score: 5
Accepted
time: 197ms
memory: 48804kb

input:

200000
48508 52931
115469 53334
53334 109332
55615 111128
160153 129069
81733 149640
69172 127972
53334 71755
107633 53334
92200 144859
191346 61711
192310 131522
144360 89737
112809 69429
24034 53334
8244 53334
134631 53334
53334 157868
179139 39842
112773 53334
131063 78546
95501 143642
50916 5333...

output:

7974890890
7974712844
7974534800
7974356758
7974178718
7974000680
7973822644
7973644610
7973632734
7973454702
7973454700
7973276670
7973098642
7973091582
7973079708
7973079706
7973079702
7973079888
7973072830
7972894804
7972894798
7972894794
7972716770
7972716758
7972538736
7972360716
7972182698
797...

result:

ok 200000 lines

Test #16:

score: 5
Accepted
time: 192ms
memory: 48752kb

input:

200000
189585 140451
189585 21397
97507 124392
189551 66778
35172 110107
34572 137133
189585 175319
68631 185609
189585 113509
195998 52967
125268 189585
189585 38545
195154 62941
22458 189585
111738 150491
181476 40967
189585 175600
183092 164108
2191 91624
189585 98869
104639 189585
189585 11160
1...

output:

7948844896
7948844894
7948666996
7948667060
7948489164
7948311270
7948133378
7948121550
7948121548
7947943658
7947943946
7947943944
7947766056
7947588170
7947588168
7947588166
7947410282
7947232400
7947054520
7946876642
7946698766
7946698764
7946520890
7946343018
7946343016
7946165146
7946165138
794...

result:

ok 200000 lines

Test #17:

score: 5
Accepted
time: 152ms
memory: 48624kb

input:

200000
52744 169423
21958 49886
107574 14898
179360 193309
52744 173255
11649 194058
52744 37299
185040 52744
173083 16183
45172 52744
111564 52744
118979 40378
16515 40367
116092 15886
21781 52744
52744 18485
155320 52744
164746 118979
52744 178385
119944 52744
183596 148338
97026 100365
154834 159...

output:

7949417986
7949414460
7949414456
7949236732
7949059010
7948881290
7948881350
7948703632
7948525916
7948525914
7948348200
7948170488
7948170514
7948163404
7947985694
7947985456
7947807748
7947807942
7947807938
7947630232
7947452528
7947452526
7947274824
7947097124
7947097136
7947097134
7947097130
794...

result:

ok 200000 lines

Test #18:

score: 5
Accepted
time: 169ms
memory: 50272kb

input:

200000
98188 97568
97568 139023
97568 145232
43972 86482
97568 76922
152654 113293
97568 187093
14560 97568
130417 25367
180256 26394
70931 175568
97568 46170
102988 88140
152897 80698
151625 97568
28288 28935
97568 184813
46246 97568
126910 118530
120407 37832
97568 130045
101579 48512
176793 92123...

output:

7947926838
7947926848
7947926846
7947926886
7947926884
7947748778
7947570674
7947570672
7947392570
7947392568
7947392566
7947392564
7947392562
7947392560
7947214460
7947214458
7947214456
7947214454
7947214452
7947036354
7947029294
7946851198
7946673104
7946495012
7946495010
7946495008
7946495006
794...

result:

ok 200000 lines

Test #19:

score: 5
Accepted
time: 164ms
memory: 49112kb

input:

200000
82514 160608
129118 74477
117781 160275
32607 77450
33384 83542
177617 190138
33384 6337
94051 17548
75494 139091
22526 33384
194668 33384
9010 33384
32463 33384
33384 81726
33384 199774
68788 33384
52181 175598
18372 33384
160069 33384
75532 3294
154793 166505
33384 84585
52141 162634
138451...

output:

7901247652
7901247650
7901069904
7901069902
7901069898
7900892154
7900714412
7900714410
7900714408
7900536668
7900536666
7900358928
7900181192
7900181188
7900003454
7899825722
7899825720
7899647990
7899648012
7899470284
7899468526
7899468528
7899290802
7899290800
7899290798
7899290796
7899290794
789...

result:

ok 200000 lines

Test #20:

score: 5
Accepted
time: 179ms
memory: 48816kb

input:

200000
123057 85473
181057 139168
139374 155981
97580 66941
139374 26235
92577 28176
53567 44615
139374 158256
139374 111698
139374 7486
167825 194890
39334 139374
124253 139374
99441 512
41950 157947
45135 122712
19652 139374
145589 139374
77187 106020
111608 128762
139374 163048
67917 139374
51654...

output:

7939722716
7939722714
7939722724
7939544582
7939544572
7939544570
7939544558
7939544784
7939544746
7939544744
7939366604
7939366602
7939188464
7939010328
7938832194
7938654062
7938654060
7938475930
7938475918
7938297790
7938119664
7938119826
7937941702
7937763580
7937763566
7937585446
7937585444
793...

result:

ok 200000 lines