QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#201697#5157. High-quality Treewhsyhyyh#WA 54ms56732kbC++141.6kb2023-10-05 16:13:372023-10-05 16:13:37

Judging History

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

  • [2023-10-05 16:13:37]
  • 评测
  • 测评结果:WA
  • 用时:54ms
  • 内存:56732kb
  • [2023-10-05 16:13:37]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+9;
int n,head[N],tot;
struct pp{int nxt,to;}g[N<<1];
void add(int u,int v){g[++tot].nxt=head[u],g[tot].to=v,head[u]=tot;}
int id[N],ans;
vector<int >v[N];
void dfs(int u,int fa){
	int cnt=0,a=0,b=0;
	for(int i=head[u];i!=-1;i=g[i].nxt){
		int v=g[i].to;if(v==fa) continue;dfs(v,u);
		cnt++;if(!a) a=v;else b=v;
	}
//	printf("%d %d %d\n",u,a,b);
	if(!cnt){
		v[id[u]].push_back(1);
		v[id[u]].push_back(1);
	//ÓÐЧ£ºv[id[u]][v[id[u]].size()-v[id[u]][0]]ÉîÖ±µ½Ä©Î² 
	}
	else if(cnt==1){
		swap(id[u],id[a]);
		for(int i=v[id[u]].size()-2;i>=v[id[u]].size()-v[id[u]][0];i--) ans+=v[id[u]][i];
		v[id[u]][0]=2;
		v[id[u]].push_back(1);
	}
	else{
		if(v[id[a]][0]<v[id[b]][0]) swap(a,b);
		swap(id[u],id[a]);
		int li;
		if(v[id[u]][0]==v[id[b]][0]) li=v[id[u]][0];
		else li=min(v[id[u]][0],v[id[b]][0])+1;
//		printf("%d\n",li);
		int j=v[id[u]].size()-1;
		for(int i=v[id[b]].size()-1;i>=max((int)v[id[b]].size()-li,1);i--){
			v[id[u]][j]+=v[id[b]][i];
//			printf("%d %d %d %d\n",id[u],id[b],j,i);
			j--;
		}
//		printf("! %d\n",v[id[u]].size()-li-1);
		for(int i=v[id[u]].size()-li-1;i>=max((int)v[id[u]].size()-(int)v[id[u]][0],1);i--){
			ans+=v[id[u]][i];
//			printf("%d")
//			printf("%d %d\n",u,v[id[u]][i]);
		}
		v[id[u]][0]=li+1;
		v[id[u]].push_back(1);
	}
//	printf("%d %d\n",u,v[id[u]][0]);
	return ;
}

int main(){
	memset(head,-1,sizeof(head));tot=0;
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v;scanf("%d%d",&u,&v);add(u,v);add(v,u);
	}	
	for(int i=1;i<=n;i++) id[i]=i;
	ans=0;
	dfs(1,0);
	printf("%d\n",ans);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 34356kb

input:

6
1 2
1 3
3 4
3 5
5 6

output:

1

result:

ok single line: '1'

Test #2:

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

input:

12
1 2
2 3
3 4
3 5
1 6
6 7
7 8
7 9
9 10
6 11
11 12

output:

3

result:

ok single line: '3'

Test #3:

score: 0
Accepted
time: 54ms
memory: 49624kb

input:

200000
167246 158246
40931 40296
178588 27974
35171 899
4204 163250
101422 9230
55420 93371
16012 140142
28866 154497
33519 180725
50361 52348
46923 175364
126599 169575
15138 34958
164256 64770
63123 130169
154172 168301
127476 54744
199964 81879
173765 69220
178225 73653
59861 46415
138112 17507
8...

output:

199998

result:

ok single line: '199998'

Test #4:

score: 0
Accepted
time: 39ms
memory: 56732kb

input:

200000
144434 24107
75087 108465
38670 156657
31235 30143
40544 44213
51188 21788
170574 164351
14169 155909
120876 119956
196361 140453
197958 142813
23944 62568
12098 71652
162226 122184
123783 86178
70076 115586
74439 94246
83296 36713
182500 16937
174946 154091
97484 194764
179943 61793
114439 1...

output:

199998

result:

ok single line: '199998'

Test #5:

score: 0
Accepted
time: 51ms
memory: 44720kb

input:

200000
42469 8516
3910 143673
129125 150433
170053 160404
147325 66173
130784 195620
183508 43943
90940 88012
187183 803
139576 36677
190280 71191
107959 177664
14308 20402
93449 130555
80315 75413
178265 104526
4428 8875
151397 91172
181321 47276
105060 81973
196326 19584
44364 56143
187070 195424
...

output:

199998

result:

ok single line: '199998'

Test #6:

score: 0
Accepted
time: 37ms
memory: 38676kb

input:

131071
94531 87688
119005 53065
70725 126770
61026 82294
114384 270
98205 38915
61461 14652
123122 36872
37639 52311
17774 89648
79899 59785
6033 52465
15449 93250
43849 18174
2665 82543
26740 15199
71645 14339
45549 119270
22896 70677
126250 23614
5796 85715
92715 25280
119740 8911
17923 5547
47703...

output:

0

result:

ok single line: '0'

Test #7:

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

input:

7
1 3
3 4
1 7
7 2
7 6
3 5

output:

0

result:

ok single line: '0'

Test #8:

score: 0
Accepted
time: 15ms
memory: 37440kb

input:

75026
12155 64806
40053 74785
70103 1220
72989 33966
74199 66365
52024 24358
54545 52118
52572 28566
68873 41146
10161 67848
41221 63589
72291 44013
51515 14784
12150 33009
3919 23413
61773 13741
21172 17759
27774 65766
58702 13619
11690 19263
45469 30662
33296 45184
51641 13235
11413 52734
74437 57...

output:

2

result:

ok single line: '2'

Test #9:

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

input:

10947
7184 5103
1433 10766
3794 8428
1438 8926
2493 7796
6753 7135
3304 4497
9148 8680
4013 2259
3067 8641
2809 9523
9557 2452
8392 3411
1121 6418
5150 133
8893 3701
7864 3044
7152 705
3856 5325
10943 4760
9792 7866
6959 6282
1120 7627
2952 9675
10407 9119
2489 1131
907 4948
4175 3572
4178 337
226 7...

output:

2

result:

ok single line: '2'

Test #10:

score: -100
Wrong Answer
time: 5ms
memory: 36508kb

input:

8375
5605 5852
7762 3219
1669 4378
341 6410
1502 1920
706 8356
5088 5723
1326 6305
2433 5341
5185 948
7639 5745
6173 7572
4736 7204
8081 3452
2414 6798
156 7332
6627 2209
876 5078
2666 292
5041 7782
7118 807
6897 5220
5865 1273
6546 1506
4306 7980
1119 6488
4795 5942
6219 7729
8119 1572
4027 4817
46...

output:

704

result:

wrong answer 1st lines differ - expected: '701', found: '704'