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;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vii> vvii;
#define task "test"
#define fastIO ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define forw(i, l, r) for( ll i = (l) ; i < (r) ; i++ )
#define forb(i, r, l) for( ll i = (r) ; i >= (l) ; i-- )
#define numBit(x) (__builtin_popcountll(1ll * (x)))
#define getBit(x, i) ((x) >> (i) & 1)
#define sz(x) (int)x.size()
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define debug(x) cerr << #x << " = " << x << '\n';
const int N = 2e5 + 7;
const ll inf = 0x3f3f3f3f;
int n, f[N];
set<int> A, B;
vi adj[N];
void dfs(int u, int p = -1) {
f[u] = 1;
for (int v: adj[u]) if (v != p) {
dfs(v, u);
f[u] += f[v];
}
}
vi find(set<int> s, int v) {
vi ret;
auto it = s.lower_bound(v);
if (it != s.end()) ret.pb(*it);
if (it != s.begin()) {
--it;
ret.pb(*it);
}
return ret;
}
int get(int x, int y, int z) {
return max(x, max(y - x, z - y)) - min(x, min(y - x, z - y));
}
int get2(int x, int y, int z) {
return max(x, max(y, z - y - x)) - min(x, min(y, z - y - x));
}
int solve(int u, int p) {
int ans = inf;
for (auto it: find(A, (n + f[u]) / 2))
ans = min(ans, get(f[u], it, n));
for (auto it: find(B, (n - f[u]) / 2))
ans = min(ans, get2(f[u], it, n));
A.insert(f[u]);
for (int v: adj[u]) if (v != p)
ans = min(ans, solve(v, u));
A.erase(f[u]), B.insert(f[u]);
return ans;
}
int main() {
fastIO;
cin >> n;
forw(i, 0, n - 1) {
int u, v; cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
dfs(1);
cout << solve(1, -1) << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |