一棵树,两个点,一个点a想尽快靠近另一个点b,一个点想尽快远离一个点,问这两个点走多少步能碰上。、
追逐过程:尽快靠近的那个点每一步都是沿最短路径靠近,尽快远离那个点每一步都朝树的边缘走去,走到边缘后就不动了,静静等待。
最长路径取决与a点走多少步,
所以我们只需要dfs 这两个点,找到两个点到任意点的距离,
从disa[ i ] ≥ disb [ i ]的点中,取这些点的dis[a]的最大值,最后乘2因为disa[ i ]只是a走过的距离,而题目要求输出a和b的总回合数。
vector<int>g[N];
int disa[N],disb[N];
void dfs(int x,int pre,int aorb)
{
for(int y:g[x])
{
if(y==pre) continue;
if(aorb==0) disa[y]=disa[x]+1;
else disb[y]=disb[x]+1;
dfs(y,x,aorb);
}
}
int main()
{
fast;
int n,a=1,b;cin>>n>>b;
rep(i,n-1)
{
int x,y;cin>>x>>y;
g[x].push_back(y),g[y].push_back(x);
}
disa[a]=disb[b]=0;
dfs(a,0,0);dfs(b,0,1);
int ans=0;
rpp(i,n) if(disa[i]>disb[i]) ans=max(ans,disa[i]);
cout<<ans*2<<'\n';
return 0;
} 
京公网安备 11010502036488号