UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#201409#3491. 最优选择JuRuoError_YBW1001729ms30176kbC++111.2kb2024-01-28 09:57:282024-01-28 12:09:00

answer

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define int long long
char freadgetchar(){
	static char buf[100000],*p1=buf,*p2=buf;
	if(p1==p2){
		p2=(p1=buf)+fread(buf,1,100000,stdin);
		if (p1==p2)return EOF;
	}
	return *p1++;
}
void read(int&x){
	static char c;
	c=freadgetchar();
	int b=1;
	for(x = 0;!(c>='0'&&c<='9');c=freadgetchar()) if(c == '-') b = -b;
	for(;c>='0'&&c<='9';x=x*10+c-'0',c=freadgetchar());x*=b;
}
const int MAXN=3e5+5;
std::vector<int> g[MAXN];
int n,ff[MAXN];
int G,mxg=1e18;
int sz[MAXN];
int d[MAXN],ans[MAXN];
void dfs1(int x,int fa){
	sz[x]=1;
	int mx=0;
	for(auto v:g[x]){
		if(v==fa)continue;
		dfs1(v,x);
		d[x]+=d[v]+sz[v];
		sz[x]+=sz[v];
		mx=std::max(mx,sz[v]);
	}
	mx=std::max(mx,n-sz[x]);
	if(mx<mxg)G=x,mxg=mx;
}
void dfs2(int x,int f){
	for(auto v:g[x]){
		if(v==f)continue;
		ans[v]=ans[x]-sz[v]+n-sz[v];
		dfs2(v,x);
	}
}
signed main(){
	std::cin>>n;
	
	for(int i=2;i<=n;i++){
		int u,v;
		std::cin>>u>>v;
		g[u].emplace_back(v);
		g[v].emplace_back(u);
	}
	dfs1(1,0);
	ans[1]=d[1];
	dfs2(1,0);
	int sum=0;
	for(int i=1;i<=n;i++){
		sum+=ans[i];
		//std::cout<<ans[i]<<'\n';
	}
	//std::cout<<G<<'\n';
	std::cout<<sum-2*ans[G]<<'\n';
	return 0;
}

详细

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

Test #1:

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

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

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

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

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

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

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

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

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: 553ms
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: 305ms
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