UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#201416#3491. 最优选择baiencheng100918ms31540kbC++1.3kb2024-01-28 10:10:272024-01-28 12:09:35

answer

#include <bits/stdc++.h>

#include <ctime>

#define int long long

#define double long double

#define INF LONG_LONG_MAX

#define maxn 300005

#define fr read()

#define pii pair<int,int>

#define eps -1e6

using namespace std;

int n;

vector<pair<int,int> > z[maxn];

int sz[maxn],ans[maxn],d[maxn];

int G,mxg = INF;

void dfs1(int x,int f){
	
	int mx = 0;
	
	sz[x] = 1;
	
	for(int i = 0;i < z[x].size();++ i){
		
		int v = z[x][i].first;
		
		if(v == f) continue;
		
		dfs1(v,x);
		
		d[x] += d[v] + sz[v];
		
		sz[x] += sz[v];
		
		mx = max(mx,sz[v]);
		
	}
	
	mx = max(mx,n - sz[x]);
	
	if(mx < mxg) G = x,mxg = mx;
	
	return ;
	
}

void dfs2(int x,int f){
	
	for(int i = 0;i < z[x].size();++ i){
		
		int v = z[x][i].first;
		
		if(v == f) continue;
		
		ans[v] = ans[x] - sz[v] + n - sz[v];
		
		dfs2(v,x);
		
	}
	
	return ;
	
}

signed main() {
	
	ios::sync_with_stdio(0);
	
	cin.tie(0);
	
	cout.tie(0);
	
	cin >> n;
	
	for(int i = 1;i < n;++ i){
		
		int s,e;
		
		cin >> s >> e;
		
		z[s].push_back({e,1});
		
		z[e].push_back({s,1});
		
	}
	
	dfs1(1,0);
	
	ans[1] = d[1];
	
	dfs2(1,0);
	
	int anss = 0;
	
	for(int i = 1;i <= n;++ i){
		
		if(i != G) anss += ans[i];
		
	} 
	
	cout << anss - ans[G] << "\n";
	
	return 0;
	
}

Details

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

Test #1:

score: 10
Accepted
time: 4ms
memory: 13292kb

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: 2ms
memory: 13292kb

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

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

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

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: 6ms
memory: 13588kb

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: 261ms
memory: 31200kb

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: 184ms
memory: 31516kb

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: 270ms
memory: 31188kb

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: 188ms
memory: 31540kb

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