一棵树,两个点,一个点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; }