UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#201398#3491. 最优选择Planting100746ms33032kbC++1.6kb2024-01-28 09:35:282024-01-28 12:07:06

answer

# include <bits/stdc++.h>

# define int long long

using namespace std;

int n;

int u[300005], v[300005];

int dep[300005]; 

vector < int > vec[300005];

inline void add (int u, int v) {
	
	vec[u].push_back (v);
	
	vec[v].push_back (u);
	
}

int ans, anss = 2147483647;

int size[300005];

inline void dfs (int u, int fa) {
	
	int sum = 0;
	
	size[u] = 1;
	
	dep[u] = dep[fa] + 1;
	
	for (int i = 0; i < vec[u].size (); ++ i) {
		
		int v = vec[u][i];
		
		if (v == fa) continue;
		
		dfs (v, u);
		
		sum = max (sum, size[v]);
		
		size[u] += size[v];
		
	}
	
	sum = max (sum, n - size[u]);
	
	if (sum < anss) {
		
		anss = sum, ans = u;
		
	}
	
}

int nw = 0;

bool vis[300005];

inline void bfs (int s) {
	
	queue < pair < int, int > > q;
	
	q.push (make_pair (s, 0));
	
	vis[s] = 1;
	
	while (! q.empty ()) {
		
		pair < int, int > uu = q.front ();
		
		int w = uu.second;
		
		int u = uu.first;
		
		q.pop ();
		
		for (int i = 0; i < vec[u].size (); ++ i) {
			
			int v = vec[u][i];
			
			if (vis[v]) continue;
			
			pair < int, int > nww = make_pair (v, w + 1);
			
			nw += w + 1;
			
			vis[v] = 1;
			
			q.push (nww);
			
		}
		
	}
	
}

signed main () {
	
	scanf ("%lld", &n);
	
	for (int i = 1; i < n; ++ i) {
	
		scanf ("%lld %lld", &u[i], &v[i]);
		
		add (u[i], v[i]);
		
	}
	
	dfs (1, 0);
	
	bfs (ans);
	
	int nwans = 0;
	
	for (int i = 1; i < n; ++ i) {
		
		if (dep[u[i]] > dep[v[i]]) swap (u[i], v[i]);
		
		nwans += 2 * size[v[i]] * (n - size[v[i]]);
		
	}
	
	printf ("%lld\n", nwans - 2 * nw);
	
	return 0;
	
}

Details

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

Test #1:

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

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

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: 4ms
memory: 13556kb

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

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

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: 1ms
memory: 13848kb

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: 177ms
memory: 28972kb

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: 191ms
memory: 33032kb

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: 205ms
memory: 28988kb

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: 154ms
memory: 32768kb

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