This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// by szh
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define F first
#define S second
#define pii pair<LL, LL>
#define pb push_back
#define debug(x) cerr << #x << "=" << x << endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a; i < (b); i++)
#define MP make_pair
#define SZ(x) (static_cast<int>(x.size()))
#define MOD 1000000007
#define ALL(x) x.begin(), x.end()
void inc(int &a, int b) {a = (a+b)%MOD;}
void dec(int &a, int b) {a = (a-b+MOD)%MOD;}
int prod(int a,int b) {return LL(a)*LL(b)%MOD;}
int lowbit(int x) {return x&(-x);}
const int maxn = 3e5+10;
int n;
vector <int> edge[maxn];
int cnt = 0;
int x, y;
int dp[maxn];
int ans = 0;
int uu, vv;
int solve(int u, int fa) {
vector <int> val;
for (auto v : edge[u]) {
if (v == fa) continue;
if (uu == u and vv == v) continue;
if (uu == v and vv == u) continue;
solve(v, u);
val.pb(dp[v]);
}
//debug(u), debug(SZ(val));
sort(ALL(val));
reverse(ALL(val));
dp[u] = 0;
rep(i, 0, SZ(val)) dp[u] = max(dp[u], val[i] + i + 1);
//debug(dp[u]);
return dp[u];
}
vector <int> node;
bool dfs(int u, int fa) {
if (u == y) node.pb(u);
if (u == y) return true;
for (int v : edge[u]) {
if (v == fa) continue;
if (dfs(v, u)) {
node.pb(u);
return true;
}
}
return false;
}
int main() {
// freopen("input.txt","r",stdin);
std::ios::sync_with_stdio(false); cin.tie(0);
memset(dp, -1, sizeof(dp));
cin >> n >> x >> y;
rep(i, 1, n) {
int u, v;
cin >> u >> v;
edge[u].pb(v);
edge[v].pb(u);
}
dfs(x, -1);
uu = -1, vv = -1;
if (SZ(node) == 2) {
ans = max(solve(x, y), solve(y, x));
cout << ans;
return 0;
}
int l = 0, r = SZ(node) - 2;
ans = n;
while (l < r) {
int mid = l + r + 1 >> 1;
uu = node[mid], vv = node[mid+1];
int tmp1 = solve(node[0], -1), tmp2 = solve(node.back(), -1);
//debug(uu), debug(vv);
//debug(dp[3]), debug(dp[4]), debug(dp[13]);
//debug(mid), debug(tmp1), debug(tmp2);
ans = min(ans, max(tmp1, tmp2));
if (tmp1 < tmp2) l = mid;
else r = mid-1;
}
l++;
if (l < SZ(node) - 1) {
uu = node[l], vv = node[l+1];
int tmp1 = solve(node[0], -1), tmp2 = solve(node.back(), -1);
ans = min(ans, max(tmp1, tmp2));
}
cout << ans << "\n";
return 0;
}
Compilation message (stderr)
torrent.cpp: In function 'int main()':
torrent.cpp:88:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
88 | int mid = l + r + 1 >> 1;
| ~~~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |