#include<bits/stdc++.h>
#define el cout<<"\n"
#define f0(i,n) for(int i=0;i<n;++i)
#define f1(i,n) for(int i=1;i<=n;++i)
#define maxn 200005
using namespace std;
int n, sz[maxn], ans = 1e9;
vector <int> a[maxn];
void dfs(int u, int p)
{
sz[u] = 1;
for (int v:a[u]) if (v!=p)
{
dfs(v, u);
sz[u] += sz[v];
}
}
set <int> A, B;
/*
set A: contain all vertices from root to parent of u
B - Root - |szA - | sz[u]: 3 parts: n - szA, szA - sz[u], sz[u]
set B: contain all vertices visited and not in A
B - | Root - | sz[u]: 3 parts: szB, n - szB - sz[u], sz[u]
*/
int optimize(int a, int b, int c)
{
return max({a, b, c}) - min({a, b, c});
}
vector <int> closest(set <int> &s, int x)
{
vector <int> v;
auto it = s.lower_bound(x);
if (it != s.end()) v.push_back(*it);
if (it != s.begin())
{
--it;
v.push_back(*it);
}
return v;
}
void dfs2(int u, int p)
{
for (int szA: closest(A, (n + sz[u])/2))
ans = min(ans, optimize(sz[u], szA - sz[u], n-szA));
for (int szB: closest(B, (n - sz[u])/2))
ans = min(ans, optimize(sz[u], szB, n-sz[u]-szB));
A.insert(sz[u]);
for (int v:a[u]) if (v!=p)
dfs2(v, u);
A.erase(sz[u]);
B.insert(sz[u]);
}
main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n;
f1 (i, n-1)
{
int u, v;
cin >> u >> v;
a[u].push_back(v);
a[v].push_back(u);
}
dfs(1, 0);
dfs2(1, 0);
cout << ans;
}
Compilation message
papricice.cpp:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
53 | main()
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5020 KB |
Output is correct |
3 |
Correct |
3 ms |
5024 KB |
Output is correct |
4 |
Correct |
4 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5020 KB |
Output is correct |
3 |
Correct |
3 ms |
5024 KB |
Output is correct |
4 |
Correct |
4 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
4 ms |
5040 KB |
Output is correct |
7 |
Correct |
4 ms |
5032 KB |
Output is correct |
8 |
Correct |
3 ms |
5076 KB |
Output is correct |
9 |
Correct |
4 ms |
5076 KB |
Output is correct |
10 |
Correct |
4 ms |
5076 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5020 KB |
Output is correct |
3 |
Correct |
3 ms |
5024 KB |
Output is correct |
4 |
Correct |
4 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
4 ms |
5040 KB |
Output is correct |
7 |
Correct |
4 ms |
5032 KB |
Output is correct |
8 |
Correct |
3 ms |
5076 KB |
Output is correct |
9 |
Correct |
4 ms |
5076 KB |
Output is correct |
10 |
Correct |
4 ms |
5076 KB |
Output is correct |
11 |
Correct |
157 ms |
14708 KB |
Output is correct |
12 |
Correct |
207 ms |
14752 KB |
Output is correct |
13 |
Correct |
159 ms |
15072 KB |
Output is correct |
14 |
Correct |
157 ms |
14864 KB |
Output is correct |
15 |
Correct |
189 ms |
14624 KB |
Output is correct |
16 |
Correct |
117 ms |
14508 KB |
Output is correct |
17 |
Correct |
166 ms |
14760 KB |
Output is correct |
18 |
Correct |
192 ms |
23444 KB |
Output is correct |
19 |
Correct |
178 ms |
14736 KB |
Output is correct |
20 |
Correct |
189 ms |
14868 KB |
Output is correct |