题解 AT5285 [ABC148F] Playing Tag on Tree

· · 题解

不难发现，如果一个点到 u 的距离小于它到 v 的距离，那么 T 就不会在这个点被 A 追到。

由此可以得到解法:

  1. 通过搜索算出 u 和 v 到树上其他点的距离（由于是树，路径唯一，只需要 bfs 或 dfs 就彳亍了）。

时间复杂度：

因为在搜索中每个点只被枚举到 1 遍，所以总体复杂度是 O(n) 的。

还有一些细节在代码里讲，上代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,u,v,du[N],dv[N],ans;
vector<int> e[N];//因为比较懒，所以用了邻接表存图
inline void dfs(int dis[],int x,int fa)
{
    for(int i=0;i<e[x].size();i++)
    {
        int v=e[x][i];
        if(v==fa) continue;
        dis[v]=dis[x]+1;
        dfs(dis,v,x);
    }
}
signed main()
{
    cin>>n>>u>>v;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        e[x].push_back(y);//无向图，建双向边
        e[y].push_back(x);
    }
    dfs(du,u,0);//算出 u 到树上其他点的距离
    dfs(dv,v,0);//算出 v 到树上其他点的距离
    for(int i=1;i<=n;i++)
    {
        if(du[i]<dv[i]) 
            ans=max(ans,dv[i]); 
    }
    cout<<ans-1;
}