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>
#define el '\n'
#define fu(i, a, b) for (long long i = a; i <= b; ++i)
#define fd(i, a, b) for (long long i = a; i >= b; --i)
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define sz(v) (ll)v.size()
#define mask(i) (1LL << i)
#define bit(x, i) ((x) >> (i) & 1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll Rand(ll l, ll r) {
return uniform_int_distribution<ll> (l, r) (rng);
}
ll last(ll msk) {return msk & (-msk);}
ll pop_cnt(ll msk) {return __builtin_popcountll(msk);}
ll ctz(ll msk) {return __builtin_ctzll(msk);}
ll lg(ll msk) {return 63 - __builtin_clzll(msk);}
template<class T1, class T2>
bool maximize(T1 &a, T2 b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template<class T1, class T2>
bool minimize(T1 &a, T2 b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T>
void print(T &a, string sep = " ", string stop = "\n") {
for (auto x : a) cout << x << sep;
cout << stop;
}
template<class T>
void compress(vector<T> &v) {
sort(all(v));
v.resize(unique(all(v)) - v.begin());
}
const long long N = 1e6 + 27, base = 311, inf = 2e18, mod = 1e9 + 19972207;
ll n, t, m, timer;
ll a[N], f[N], par[N], del[N];
vector<ll> adj[N];
vector<pair<ll, ll>> save;
void update(ll &a, ll &b, ll c) {
if (a < c) {
b = a;
a = c;
}
else maximize(b, c);
}
void dfs(ll u) {
ll fi = 0, se = 0;
f[u] = sz(adj[u]) - 1;
if (u != t) del[u] = sz(adj[u]) - 2 + del[par[u]] + (u == m);
for (ll v : adj[u]) {
if (v == par[u]) continue;
par[v] = u;
dfs(v);
update(fi, se, f[v]);
}
f[u] += se;
}
bool check(ll x) {
ll block = 0;
for (pair<ll, ll> tmp : save) {
if (tmp.ss > x) {
if (block + 1 > tmp.ff) return false;
block++;
x--;
}
}
return x >= 0;
}
signed main() {
// freopen("brentford40mu.inp", "r", stdin);
// freopen("brentford40mu.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> t >> m;
if (t == m) return cout << 0, 0;
fu(i, 2, n) {
ll u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(t);
ll cnt = 0, pre = 0;
while (t != m) {
for (ll v : adj[m]) {
if (v != par[m] && v != pre) save.push_back(make_pair(cnt + 1, f[v] + del[m]));
}
cnt++;
pre = m;
m = par[m];
}
// fu(i, 1, n) cout << del[i] << ' ';
sort(all(save));
// cout << el;
// for (pair<ll, ll> tmp : save) cout << tmp.ff << ' ' << tmp.ss << el;
ll l = 0, r = 2 * n;
while (l < r) {
ll mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |