UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#201412#3491. 最优选择CheZiHe9291001013ms33056kbC++111.3kb2024-01-28 10:06:262024-01-28 12:09:15

answer

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
const int MAXN=3e5+5;

int n,dep[MAXN],siz[MAXN];
int s[MAXN],e[MAXN];
int root,minn=INT_MAX,ans1,ans2;
bool vis[MAXN];
std::vector<int> v[MAXN];
void add(int s,int e){v[s].push_back(e);v[e].push_back(s);}

void solve1(int x,int fa){
	int maxn=-1;
	siz[x]=1;
	dep[x]=dep[fa]+1;

	for(int i=0;i<v[x].size();i++)
		if(v[x][i]!=fa){
			solve1(v[x][i],x);
			siz[x]+=siz[v[x][i]];
			maxn=std::max(maxn,siz[v[x][i]]);
		}
	maxn=std::max(maxn,n-siz[x]);
	if(maxn<minn){
		minn=maxn;
		root=x;
	}
}

void solve2(int s){
	std::queue<std::pair<int,int> > q;
	q.push({s,0});
	vis[s]=1;

	while(q.size()){
		int x=q.front().first;
		int w=q.front().second;
		q.pop();
		
		for(int i=0;i<v[x].size();i++)
			if(!vis[v[x][i]]){
				vis[v[x][i]]=1;
				std::pair<int,int> now={v[x][i],w+1};
				ans1+=w+1;
				q.push(now);
			}
	}
}

signed main () {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cin>>n;
	for(int i=1;i<n;i++){
		std::cin>>s[i]>>e[i];
		add(s[i],e[i]);
	}

	solve1(1,0);
	solve2(root);

	for(int i=1;i<n;i++){
		if(dep[s[i]]>dep[e[i]])std::swap(s[i],e[i]);
		ans2+=siz[e[i]]*(n-siz[e[i]])*2;
	}

	std::cout<<ans2-2*ans1<<endl;
	return 0;
}

Details

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

Test #1:

score: 10
Accepted
time: 5ms
memory: 15608kb

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

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

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

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

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

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

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

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

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