UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#201400#3491. 最优选择I_am_kunzi100757ms26060kbC++1.6kb2024-01-28 09:41:212024-01-28 12:07:37

answer

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<list>
#include<limits.h>
using namespace std;
vector < int > v[300005];
long long treesize[300005];
long long maxxtree = INT_MAX;
int g;
int n;
long long dis_tree[300005];
long long dis_all[300005];
void dfs(int nowx , int fa)
{
	treesize[nowx] = 1;
	long long maxxsize = 0;
	for(int i = 0 ; i < v[nowx].size() ; i++)
	{
		if(v[nowx][i] == fa)
		{
			continue;
		}
		dfs(v[nowx][i] , nowx);
		treesize[nowx] += treesize[v[nowx][i]];
		dis_tree[nowx] += dis_tree[v[nowx][i]] + treesize[v[nowx][i]];
		maxxsize = max(maxxsize , treesize[v[nowx][i]]);
	}
	maxxsize = max(maxxsize , n - treesize[nowx]);
	if(maxxsize < maxxtree)
	{
		maxxtree = maxxsize;
		g = nowx;
	}
}
void calc_dis(int nowx , int fa)
{
	for(int i = 0 ; i < v[nowx].size() ; i++)
	{
		if(v[nowx][i] == fa)
		{
			continue;
		}
		dis_all[v[nowx][i]] = dis_all[nowx] - treesize[v[nowx][i]] + (n - treesize[v[nowx][i]]);
		calc_dis(v[nowx][i] , nowx);
	}
}
signed main()
{
	scanf("%d" , &n);
	for(int i = 1 ; i < n ; i++)
	{
		int x , y;
		scanf("%d%d" , &x , &y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1 , 0);
	dis_all[1] = dis_tree[1];
	calc_dis(1 , 0);
	long long ans = 0;
	for(int i = 1 ; i <= n ; i++)
	{
		if(i == g)
		{
			ans -= dis_all[i];
		}
		else
		{
			ans += dis_all[i];
		}
	}
	cout << ans << endl;
	return 0;
}

详细

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

Test #1:

score: 10
Accepted
time: 3ms
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: 0ms
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: 4ms
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: 3ms
memory: 13496kb

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

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

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

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

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

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

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