#include <bits/stdc++.h>
#define smile "TDL."
#define mp make_pair
using namespace std;
typedef pair<int, int> ii;
typedef long long ll;
const int N = (int) 3e5 + 10;
int n, m;
vector<int> g[N];
int M[3];
int f[N];
int c[N];
ii banned = mp(0,0);
void dfs(int u, int pre)
{
vector<int> tmp;
f[u] = 0;
c[u] = 0;
for (int v: g[u])
{
if (v == pre || mp(min(u, v), max(u, v)) == banned) continue;
dfs(v, u);
c[u]++;
tmp.push_back(f[v]);
}
sort(tmp.begin(), tmp.end(), greater<int>());
for (int i = 0; i < tmp.size(); i++)
f[u] = max(f[u], tmp[i]+i+1);
}
namespace SUB2
{
void solve()
{
dfs(M[0], M[0]);
cout << f[M[0]];
}
}
namespace SUB4
{
int trace[N];
void bfs(int s, int t)
{
queue<int> q;
q.push(s);
trace[s] = -1;
while (!q.empty())
{
int u = q.front(); q.pop();
for (int v: g[u])
{
if (!trace[v])
{
trace[v] = u;
q.push(v);
if (v == t) return;
}
}
}
}
vector<ii> e;
vector<int> tmp;
int calc(int u, int v)
{
banned = mp(min(u, v), max(u,v));
dfs(M[1], M[1]);
dfs(M[0], M[0]);
cerr << "cute";
int t1 = f[M[0]], t2 = f[M[1]];
if (t1 < t2)
t1 += (c[M[0]] == t1);
else if (t2 < t1)
t2 += (c[M[1]] == t2);
else if (c[M[0]] == t1 && c[M[1]] == t2)
t1++;
return max(t1, t2);
}
int ans = INT_MAX;
bool ok()
{
dfs(M[1], M[1]);
dfs(M[0], M[0]);
int t1 = f[M[0]], t2 = f[M[1]];
if (t1 < t2)
t1 += (c[M[0]] == t1);
else if (t2 < t1)
t2 += (c[M[1]] == t2);
else if (c[M[0]] == t1 && c[M[1]] == t2)
t1++;
ans = min(ans, max(t1, t2));
return t1 < t2;
}
void T()
{
int tl = calc(tmp[0], tmp[1]),
tr = calc(tmp[tmp.size()-2], tmp[tmp.size()-1]);
int l = 1, r = tmp.size()-2;
/*
for (int i = 17; i >= 0; i--)
{
if (l + (1 << i) > r) continue;
int j = l + (1 << i);
int u = tmp[j], v = tmp[j-1];
if (calc(u, v) == tl) l += (1 << i);
}
for (int i = 17; i >= 0; i--)
{
if (r - (1 << i) < l) continue;
int j = r - (1 << i);
int u = tmp[j], v = tmp[j+1];
if (calc(u, v) == tr) r -= (1 << i);
}
for (int i = 17; i >= 0; i--)
{
if (l + (1 << i) > r) continue;
int j = l + (1 << i);
int s = tmp[j-1], u = tmp[j], v = tmp[j+1];
if (calc(s, u) > calc(u, v)) l += (1 << i);
}
for (int i = 17; i >= 0; i--)
{
if (l + (1 << i) > r) continue;
int j = r - (1 << i);
int s = tmp[j-1], u = tmp[j], v = tmp[j+1];
if (calc(s, u) < calc(u, v)) r -= (1 << i);
}
for (int i = l-1; i <= r; i++)
ans = min(ans, calc(tmp[i], tmp[i+1]));
*/
while (l <= r)
{
int m = (l + r) >> 1;
banned = mp(min(tmp[m], tmp[m-1]), max(tmp[m], tmp[m-1]));
if (ok())
l = m + 1;
else
r = m - 1;
}
// cout << l << ' ' << r << '\n';
cout << ans;
}
void solve()
{
int ans = INT_MAX;
bfs(M[0], M[1]);
int v = M[1];
while (v != -1)
{
tmp.push_back(v);
v = trace[v];
}
reverse(tmp.begin(), tmp.end());
T();
}
}
int main()
{
// freopen(smile"inp", "r", stdin);
// freopen(smile"out", "w", stdout);
// time_t bg = clock();
cin.tie(0) -> sync_with_stdio(0);
cin >> n >> M[0] >> M[1];
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
// cin >> m;
// for (int i = 0; i < m; i++)
// cin >> M[i];
// if (m == 1)
// SUB2::solve();
// else
SUB4::solve();
// cerr << '\n' << setprecision(5) << fixed << (double) (clock() - bg) / CLOCKS_PER_SEC;
return 0;
}
Compilation message
torrent.cpp: In function 'void dfs(int, int)':
torrent.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for (int i = 0; i < tmp.size(); i++)
| ~~^~~~~~~~~~~~
torrent.cpp: In function 'void SUB4::T()':
torrent.cpp:100:13: warning: unused variable 'tl' [-Wunused-variable]
100 | int tl = calc(tmp[0], tmp[1]),
| ^~
torrent.cpp:101:13: warning: unused variable 'tr' [-Wunused-variable]
101 | tr = calc(tmp[tmp.size()-2], tmp[tmp.size()-1]);
| ^~
torrent.cpp: In function 'void SUB4::solve()':
torrent.cpp:149:13: warning: unused variable 'ans' [-Wunused-variable]
149 | int ans = INT_MAX;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
7516 KB |
Output is correct |
| 2 |
Correct |
3 ms |
7516 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7516 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
226 ms |
28756 KB |
Output is correct |
| 2 |
Correct |
254 ms |
31824 KB |
Output is correct |
| 3 |
Correct |
235 ms |
31980 KB |
Output is correct |
| 4 |
Correct |
263 ms |
34252 KB |
Output is correct |
| 5 |
Correct |
234 ms |
28584 KB |
Output is correct |
| 6 |
Correct |
231 ms |
28508 KB |
Output is correct |
| 7 |
Correct |
237 ms |
34068 KB |
Output is correct |
