<题目链接>

题目大意：
A、B两人在一颗树上，A在根节点1上，B在节点x上，现在他们轮流走，每次只能走一步，或者不走。A以尽可能靠近B的方式行走，B以尽可能远离A的方式走，B先开始走。问你这两人相遇时，总共走了多少步。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

解题分析：

模拟A、B走路的过程可以发现，其实A、B走路的步数就是在B所能够到达的点中，距离A最远的点*2。所谓B能够到达的点就是，B到达这个点的最短时间一定要小于A达到这个点的最短时间。否则B就会在这个点出被A抓住。因为是B先走，所以B只要走那些比A先到的节点，就一定只会和A在距A最远的叶子节点相遇，因为B到了那个叶子节点之后，一定会选择一直不动，所以A、B相遇的时间就如上面所述。

#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T&x){
    x=0;int f=1;char c=getchar();
    while(c<'0' || c>'9'){ if(c=='-')f=-1;c=getchar(); }
    while(c>='0' && c<='9'){ x=x*10+c-'0';c=getchar(); }
    x*=f;
}
const int N = 2e5+5;
const int INF = 0x3f3f3f3f;

int n,x,ans,cnt,loc;
int head[N],d1[N],d2[N],vis[N];
struct Edge{ int to,nxt; }e[N<<1];

inline void add(int u,int v){
    e[++cnt]=(Edge){v,head[u]};
    head[u]=cnt;
}
void bfs1(int st){      //将根节点到所有点的最短距离全部求出来
    memset(d1,0x3f,sizeof(d1));
    d1[st]=0;
    queue<int>q;
    q.push(st);vis[st]=1;
    while(q.size()){         
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(vis[v])continue;
            d1[v]=d1[u]+1;
            vis[v]=1;
            q.push(v);
        }
    }
}
void bfs2(int st){     //将x能够到达的所有点的最短距离求出来
    memset(d2,0x3f,sizeof(d2));
    memset(vis,0,sizeof(vis));
    d2[st]=0;vis[st]=1;ans=d1[st];
    queue<int>q;q.push(st);
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(vis[v]||(d2[u]+1)>=d1[v])continue;    //如果到达该点的时间晚于1节点到达的时间
            d2[v]=d2[u]+1;vis[v]=1;
            //此时v点B能够到达
            ans=max(ans,d1[v]);
            q.push(v);
        }
    }
}
int main(){
    read(n);read(x);
    for(int i=1;i<n;i++){
        int u,v;read(u);read(v);
        add(u,v);add(v,u);
    }
    bfs1(1);
/*    for(int i=1;i<=n;i++){
        printf("i=%d,d1=%d\n",i,d1[i]);
    }   */
    bfs2(x);
    printf("%d\n",2*ans);
}

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄