#include "bits/stdc++.h"
using namespace std;
void open_file(const string &file_name) {
if (fopen((file_name + ".inp").c_str(), "r")) {
freopen((file_name + ".inp").c_str(), "r", stdin);
freopen((file_name + ".out").c_str(), "w", stdout);
}
}
void init();
void solve();
bool multitest();
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
clock_t TIME = clock();
init();
int TEST = 1;
if (multitest()) cin >> TEST;
while (TEST--) solve();
cerr << "\nUsed: " << clock() - TIME << " ms\n\n";
}
bool multitest() {
return 0;
}
const int NM = 2e5 + 5;
int n, sz[NM], ans = INT_MAX;
vector<int> adj[NM];
set<int> a[NM], b;
bool visited[NM];
int C(set<int> &m, int x) {
auto k = m.lower_bound(x);
int mi = INT_MAX, res;
if (k != m.end() && mi > abs(x - *k)) {
mi = abs(x - *k);
res = *k;
}
if (k != m.begin()) {
--k;
if (mi > abs(x - *k)) {
mi = abs(x - *k);
res = *k;
}
}
return res;
}
int D(int x, int y, int z) {
return max(max(x, y), z) - min(min(x, y), z);
}
void dfs_sz(int u) {
sz[u] = 1;
for (auto &v: adj[u])
if (!sz[v]) {
dfs_sz(v);
sz[u] += sz[v];
}
}
void dfs(int u) {
visited[u] = 1;
if (b.size()) {
int tmp = C(b, (n - sz[u]) / 2);
ans = min(ans, D(sz[u], tmp, n - sz[u] - tmp));
}
for (auto &v: adj[u])
if (!visited[v]) {
dfs(v);
b.insert(v);
if (a[u].size() < a[v].size())
swap(a[u], a[v]);
for (auto &i: a[v])
a[u].insert(i);
}
a[u].insert(sz[u]);
int tmp = C(a[u], sz[u] / 2);
ans = min(ans, D(tmp, sz[u] - tmp, n - sz[u]));
}
void solve() {
cin >> n;
for (int x, y, i = 1; i < n; ++i) {
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
dfs_sz(1);
dfs(1);
cout << ans;
}
void init() {
}
Compilation message
papricice.cpp: In function 'void open_file(const string&)':
papricice.cpp:5:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | freopen((file_name + ".inp").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
papricice.cpp:6:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
6 | freopen((file_name + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
papricice.cpp: In function 'int C(std::set<int>&, int)':
papricice.cpp:51:12: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
51 | return res;
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
14684 KB |
Output is correct |
2 |
Incorrect |
3 ms |
14852 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
14684 KB |
Output is correct |
2 |
Incorrect |
3 ms |
14852 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
14684 KB |
Output is correct |
2 |
Incorrect |
3 ms |
14852 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |