[ABC148F] Playing Tag on Tree

kkxacj · 2023-08-14 11:10:10 · 题解

题目传送门

思路

考虑记录所有点到 u 和到 v 的最短距离，由于只有 n - 1 条边，dfs 即可，如果 i 到 v 的距离 小于 i 到 u 的距离，说明 T 不可能会来这里，因为 T 要尽可能活的久，而且 A 要早点抓住 T，由于问的是 A 的行走次数，所以最后答案要减一。

献上 20 行代码：

code

#include<bits/stdc++.h>
using namespace std;
int n,u,v,x,y,v2[114514],v1[114514],ma;
vector<int>w[100010];
void dfs(int xx,int yy,int z){
    if(z) v1[xx] = yy;
    else v2[xx] = yy;
    for(int i = 0;i < w[xx].size();i++){
        if(z && !v1[w[xx][i]] && w[xx][i] != v) dfs(w[xx][i],yy + 1,z);
        else if(!z && !v2[w[xx][i]] && w[xx][i] != u) dfs(w[xx][i],yy + 1,z);
    }
}
int main(){
    scanf("%d%d%d",&n,&u,&v);
    for(int i = 1;i < n;i++) scanf("%d%d",&x,&y),w[x].push_back(y),w[y].push_back(x);
    dfs(v,0,1); dfs(u,0,0); 
    for(int i = 1;i <= n;i++)  if(v1[i] > v2[i]) ma = max(ma,v1[i]);
    printf("%d",ma - 1);
    return 0;
}