#include <bits/stdc++.h>
#define quan160607 "BoundSeq"
#define fi first
#define se second
#define pii pair<int, int>
#define pb push_back
using namespace std;
typedef long long ll;
const int inf = 2e9;
const ll oo = 1e18;
const int nmax = 3e5 + 5;
void start()
{
// freopen(quan160607".inp","r",stdin);
// freopen(quan160607".out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int n, a, b, vis[nmax];
int x, y;
vector<int> v[nmax];
queue<pii> q;
int valA[nmax], valB[nmax], h[nmax], p[nmax];
vector<int> road, roadA, roadB;
void pre_dfs(int u, int par)
{
for(auto x : v[u])
{
if(x != par)
{
p[x] = u;
h[x] = h[u] + 1;
pre_dfs(x, u);
}
}
}
int find_lca(int a, int b)
{
while(h[a] > h[b])
{
roadA.push_back(p[a]);
a = p[a];
}
if(a == b) return a;
while(p[a] != p[b])
{
roadA.push_back(p[a]);
roadB.push_back(p[b]);
a = p[a];
b = p[b];
}
roadA.push_back(p[a]);
return p[a];
}
int dp[nmax], ta, tb;
void dfs(int u, int par)
{
vector<int> vv;
for(auto x : v[u])
{
if((u == ta && x == tb) || (x == ta && u == tb) || (x == par))
continue;
dfs(x, u);
vv.push_back(dp[x]);
}
if(vv.size() == 0) return;
sort(vv.begin(), vv.end(), greater<int>());
for(int i = 0; i < vv.size(); i++)
{
dp[u] = max(dp[u], vv[i] + i + 1);
// cout << u << " " << vv[i] << " " << i + 1 << "\n";
}
}
int main()
{
start();
cin >> n >> a >> b;
for(int i = 1; i <= n - 1; i++)
{
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
p[1] = 1;
h[1] = 1;
pre_dfs(1, 1);
if(h[a] < h[b])
swap(a, b);
roadA.push_back(a);
roadB.push_back(b);
int lca = find_lca(a, b);
for(int i = 0; i < roadA.size(); i++)
{
road.push_back(roadA[i]);
}
for(int i = roadB.size() - 1; i >= 0; i--)
{
if(roadB[i] == lca)
continue;
road.push_back(roadB[i]);
}
// for(auto x : road)
// cout << x << " ";
// cout << "\n";
int mid, l = 0, r = road.size() - 2; // 0 1 2 3
int ans = inf;
while(l <= r)
{
int mid = (l + r) >> 1;
ta = road[mid], tb = road[mid + 1];
memset(dp, 0, sizeof(dp));
dfs(a, a);
dfs(b, b);
// cout << mid << " " << dp[a] << " " << dp[b] << "\n";
ans = min(ans, max(dp[a], dp[b]));
if(dp[a] > dp[b])
r = mid - 1;
else
l = mid + 1;
}
cout << ans;
}
Compilation message
torrent.cpp: In function 'void dfs(int, int)':
torrent.cpp:72:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int i = 0; i < vv.size(); i++)
| ~~^~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:96:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int i = 0; i < roadA.size(); i++)
| ~~^~~~~~~~~~~~~~
torrent.cpp:109:9: warning: unused variable 'mid' [-Wunused-variable]
109 | int mid, l = 0, r = road.size() - 2; // 0 1 2 3
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
13404 KB |
Output is correct |
| 2 |
Correct |
3 ms |
13404 KB |
Output is correct |
| 3 |
Correct |
3 ms |
13400 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
289 ms |
25400 KB |
Output is correct |
| 2 |
Correct |
314 ms |
27076 KB |
Output is correct |
| 3 |
Correct |
268 ms |
28164 KB |
Output is correct |
| 4 |
Correct |
281 ms |
28108 KB |
Output is correct |
| 5 |
Correct |
241 ms |
24912 KB |
Output is correct |
| 6 |
Correct |
269 ms |
25272 KB |
Output is correct |
| 7 |
Correct |
270 ms |
28568 KB |
Output is correct |
