This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
#define f first
#define s second
#define LOGN 21
const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 100;
vector<vector<int>> graph;
int N, sz[MAXN];
multiset<int> top, st[MAXN];
void dfs(int node, int parent) {
sz[node] = 1;
for (auto u : graph[node]) {
if (u == parent)
continue;
dfs(u, node);
sz[node] += sz[u];
}
}
int ans = 1e9;
void dfs2(int node, int parent) {
if (top.size()) {
auto Q = top.lower_bound((N + sz[node]) / 2);
if (Q != top.end()) {
int x = *Q;
ans = min(ans, max({sz[node], N - x, x - sz[node]}) - min({sz[node], N - x, x - sz[node]}));
}
if (Q != top.begin()) {
int x = *prev(Q);
ans = min(ans, max({sz[node], N - x, x - sz[node]}) - min({sz[node], N - x, x - sz[node]}));
}
}
top.insert(sz[node]);
for (auto u : graph[node]) {
if (u == parent)
continue;
dfs2(u, node);
}
top.erase(top.find(sz[node]));
}
void dfs3(int node, int parent) {
for (auto u : graph[node]) {
if (u == parent)
continue;
dfs3(u, node);
if (st[u].size() > st[node].size())
swap(st[u], st[node]);
for (auto u : st[u]) {
auto Q = st[node].lower_bound((N - u) / 2);
if (Q != st[node].end()) {
int x = *Q;
ans = min(ans, max({x, u, N - x - u}) - min({x, u, N - x - u}));
}
if (Q != st[node].begin()) {
int x = *prev(Q);
ans = min(ans, max({x, u, N - x - u}) - min({x, u, N - x - u}));
}
}
}
st[node].insert(sz[node]);
}
int main() {
fast;
int a, b;
cin >> N;
graph = vector<vector<int>>(N+1, vector<int>());
for (int i = 1; i < N; i++) {
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
dfs(1, 1);
dfs2(1, 1);
dfs3(1, 1);
cout << ans << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |