#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const ll nmax=3e5+5;
int n, a, b, dp[nmax], now, ans = 1e9;
vector<int> g[nmax], vt[nmax], res;
bool vis[nmax];
pair<int, int> p;
bool kt(int u, int v)
{
if(u == p.fi && v == p.se)
return false;
if(u == p.se && v == p.fi)
return false;
return true;
}
void dis(int u)
{
vis[u] = true;
if(u == b)
{
dp[b] = 1;
res.push_back(b);
return;
}
for(auto v: g[u])
{
if(!vis[v])
{
dis(v);
dp[u] += dp[v];
}
}
if(dp[u] != 0) res.push_back(u);
}
void dfs(int u)
{
vt[u].clear();
dp[u]=1;
for(auto v:g[u])
{
if(dp[v] == 0 && kt(u, v))
{
dfs(v);
vt[u].push_back(dp[v]);
}
}
sort(vt[u].begin(), vt[u].end(), greater<int>());
for(int i=0; i<vt[u].size(); i++)
dp[u]=max(dp[u], vt[u][i]+1+i);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>a>>b;
for(int x, y, i=1; i<n; i++)
{
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
dis(a);
int l=0, r=res.size()-2, mid;
while(l <= r)
{
mid = (l+r)/2;
memset(dp, 0, sizeof(dp));
p = {res[mid], res[mid+1]};
dfs(a), dfs(b);
if(dp[a] > dp[b]) r = mid-1;
else l = mid+1;
now = max(dp[a]-1, dp[b]-1);
ans = min(ans, now);
}
cout<<ans;
}
Compilation message
torrent.cpp: In function 'void dfs(int)':
torrent.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i=0; i<vt[u].size(); i++)
| ~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
4 ms |
15704 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
318 ms |
31312 KB |
Output is correct |
2 |
Correct |
290 ms |
32992 KB |
Output is correct |
3 |
Correct |
280 ms |
34508 KB |
Output is correct |
4 |
Correct |
262 ms |
34356 KB |
Output is correct |
5 |
Correct |
261 ms |
31712 KB |
Output is correct |
6 |
Correct |
235 ms |
32336 KB |
Output is correct |
7 |
Correct |
212 ms |
36812 KB |
Output is correct |