UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#201391#3491. 最优选择LDM0116100641ms14088kbC++11971b2024-01-28 09:21:412024-01-28 12:05:56

answer

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
namespace ldm{
	int n,h[300001],cnt;
	ll sz[300001],d[300001],ans[300001],w,k=inf;
	struct node{
		int to,next;
	}a[600001];
	inline void hb(int x,int y){
		cnt++;
		a[cnt].to=y;
		a[cnt].next=h[x];
		h[x]=cnt;
	}
	inline void dfs(int x,int pre){
		sz[x]=1;
		for(int i=h[x];i!=0;i=a[i].next){
			int y=a[i].to;
			if(y==pre) continue;
			dfs(y,x);
			sz[x]+=sz[y];
			d[x]+=d[y]+sz[y];
		}
	}
	inline void dfs2(int x,int pre){
		w+=ans[x],k=min(k,ans[x]);
		for(int i=h[x];i!=0;i=a[i].next){
			int y=a[i].to;
			if(y==pre) continue;
			ans[y]=ans[x]-sz[y]+n-sz[y];
			dfs2(y,x);
		}
	}
	int main(){
		scanf("%d",&n);
		for(int i=1;i<n;i++){
			int x,y;
			scanf("%d%d",&x,&y);
			hb(x,y),hb(y,x);
		}
		dfs(1,0);
		ans[1]=d[1];
		dfs2(1,0);
		printf("%lld",w-2*k);
		return 0;
	}
}
int main(){
	ldm::main();
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 3272kb

input:

300
295 292
73 103
205 68
183 162
15 24
154 115
111 35
138 281
126 147
174 287
280 25
28 69
90 80
24...

output:

2075896

result:

ok single line: '2075896'

Test #2:

score: 10
Accepted
time: 0ms
memory: 3276kb

input:

300
143 34
175 34
286 37
291 170
136 266
130 34
94 170
83 174
152 174
167 288
8 34
161 266
238 138
1...

output:

312592

result:

ok single line: '312592'

Test #3:

score: 10
Accepted
time: 0ms
memory: 3276kb

input:

300
228 198
203 282
103 203
152 283
273 122
292 132
69 125
188 82
280 196
286 8
121 145
207 223
168 ...

output:

2350364

result:

ok single line: '2350364'

Test #4:

score: 10
Accepted
time: 2ms
memory: 3456kb

input:

5000
1951 4165
836 450
4363 279
4766 3557
4243 989
1800 666
552 2706
1853 1377
2203 4090
4169 360
42...

output:

125904196

result:

ok single line: '125904196'

Test #5:

score: 10
Accepted
time: 2ms
memory: 3452kb

input:

5000
3104 1410
2883 4771
4271 2227
1426 4048
4505 4763
207 4625
2556 1573
4644 4325
357 1616
3918 13...

output:

1596577980

result:

ok single line: '1596577980'

Test #6:

score: 10
Accepted
time: 3ms
memory: 3452kb

input:

5000
4284 4090
2775 3341
2597 4048
3286 4927
2948 2124
2891 4948
2837 1831
976 4877
2365 1990
2077 3...

output:

129275764

result:

ok single line: '129275764'

Test #7:

score: 10
Accepted
time: 166ms
memory: 14088kb

input:

300000
104582 234120
292537 276357
198762 284891
179112 115090
62779 26517
188850 227557
214063 2553...

output:

18577987869700

result:

ok single line: '18577987869700'

Test #8:

score: 10
Accepted
time: 139ms
memory: 14080kb

input:

300000
236502 215399
74568 67877
148657 58296
286895 238209
258616 295461
80299 144986
10561 115692
...

output:

660904179192

result:

ok single line: '660904179192'

Test #9:

score: 10
Accepted
time: 172ms
memory: 14084kb

input:

300000
84840 209344
63910 250801
256535 15383
284136 271103
158098 24328
161876 20374
7179 193692
25...

output:

17203414483972

result:

ok single line: '17203414483972'

Test #10:

score: 10
Accepted
time: 157ms
memory: 14080kb

input:

300000
250759 194662
232378 62498
86536 71427
281390 292867
147250 76358
5585 163671
83009 91839
405...

output:

659995157552

result:

ok single line: '659995157552'

Extra Test:

score: 0
Extra Test Passed