题解：AT_abc148_f [ABC148F] Playing Tag on Tree

mxjz666 · 2024-07-08 11:06:42 · 题解

思路

跑两次最短路，一次以逃跑者为根，一次以追捕者为根，如果在 i 号节点追捕者到这里的时间小于逃跑者到这里的时间，那么更新答案。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,su,sv,u[N],v[N],ans;
vector<int> edge[N];
void dfs(int dis[],int x,int fa){
    for(auto i:edge[x]){
        if(i==fa){
            continue;
        }
        dis[i]=dis[x]+1;
        dfs(dis,i,x);
    }
    return;
}
signed main(){
    scanf("%lld%lld%lld",&n,&su,&sv);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%lld%lld",&x,&y);
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    dfs(u,su,0);
    dfs(v,sv,0);
    for(int i=1;i<=n;i++){
        if(u[i]<v[i]){
            ans=max(ans,v[i]); 
        }
    }
    printf("%lld",ans-1);
    return 0;
}