#include <iostream>
#include <vector>
using namespace std;
const int N=1e6+2;
vector<int> ma[N];
int dp[N]; // dp[x] = def = what is the minimum number of step(Of Kalu ustad) return back to x,such that the subtree of x are the only cities you can go to
int n,t,m;
void dfs(int x,int p=-1)
{
if(x==t)
{
dp[x]=0;
return;
}
int total=0;
for(auto y:ma[x])
{
if(y!=p)
{
dfs(y,x);
total++;
}
}
int mx=0;
int mx2=0;
for(auto y:ma[x])
{
if(y!=p)
{
dp[y]++;
if(dp[y]>mx)
{
mx2=mx;
mx=dp[y];
}
else if(dp[y]>mx2)
{
mx2=dp[y];
}
}
}
if(total==0)
{
dp[x]=0;
return;
}
dp[x]=mx2+total-1;
}
int main()
{
cin>>n>>t>>m;
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
ma[x].push_back(y);
ma[y].push_back(x);
}
dfs(t);
cout<<dp[m]+1<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
25436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
525 ms |
70284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
25436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
25436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
