UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#201418#3491. 最优选择shiruiheng100925ms30176kbC++11874b2024-01-28 10:10:592024-01-28 12:10:08

answer

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define N 300010
//using LL = __int128
ll n, u, v, g, sz[N], dis[N], fa[N], sum[N];
vector<ll> e[N];
void dfs(int u, int f){
	fa[u] = f;
	sz[u] = 1;
	for(auto v : e[u]){
		if(f == v)
			continue;
		dfs(v, u);
		dis[u] += dis[v] + sz[v];
		sz[u] += sz[v];
	}
}
void dfs2(int u, int f){
	for(auto v : e[u]){
		if(f == v)
			continue;
		sum[v] = sum[u] + n - 2ll * sz[v];
		dfs2(v, u);
	}
}
int main(){
	scanf("%lld", &n);
	for(int i = 1 ; i < n ; i++){
		scanf("%lld%lld", &u, &v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1, 1);
	sum[1] = dis[1];
	g = 1;
	dfs2(1, 1);
	ll ans = 0;
	for(int i = 1 ; i <= n ; i++){
		ans += sum[i];
		if(sum[i] < sum[g])
			g = i;
		//cout << sum[i] << " \n"[i == n];
	}
	printf("%lld", ans - sum[g] * 2ll);
	return 0;
}

Details

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

Test #1:

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

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: 15584kb

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: 15584kb

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: 0ms
memory: 15776kb

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: 3ms
memory: 15756kb

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: 0ms
memory: 15776kb

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: 203ms
memory: 28592kb

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: 145ms
memory: 30164kb

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: 252ms
memory: 28600kb

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: 322ms
memory: 30176kb

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