题解：AT_abc148_f [ABC148F] Playing Tag on Tree

· · 题解

思路

方便说明，我们令追的人是 A，被追的人是 B。

我们定根方便讨论。令 A 是根。

我们肯定想要 B 尽可能的往最远的点走，走到之后来回走即可。

所以我们要先处理出来 B 点能走到的点的步数，这样就可以求出距离 B 的最远点。

放个图方便理解下（图有点丑大佬轻喷）。

这时 B 点肯定会走到它父亲节点，然后往里深入。不然就会被 A 抓到，且不是最优。

所以判断 B 满足条件的点的集合中，离 A 最远的点，在同一步数的前提下，A 能走到的最远点不包括 B 点经过的点。

所以我们还要处理 A 能走到的点的步数。

最终答案就是满足上述条件的前提下，离 B 点最远的点，与 B 点的距离。

注意，最终答案要减去一。为什么？

因为 B 最终到的点肯定不是最远那个点，而是最远那个点的前面一个点。毕竟 A，B 的轮次不一样。我们可以用反证法。如果 B 最终到了最远点并且被 A 抓住，那么证明在上一步，B 和 A 也在一起，不然就不会一起走到最深一个点，那么就不合法了。

注意一下，我代码的 A 和 B 顺序是相反的了。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;

int n, s, t, u1, v1, A, B, disA[N], disB[N], ans=0;
vector<int> a[N];
void dfs(int u, int fa)
{
    for (int i=0; i<a[u].size(); i++)
    {
        int v=a[u][i];
        if (v==fa) continue;

        disA[v]=disA[u]+1;
        dfs(v, u);
    }
}
void dfs2(int u, int fa)
{
    for (int i=0; i<a[u].size(); i++)
    {
        int v=a[u][i];
        if (v==fa) continue;

        disB[v]=disB[u]+1;
        dfs2(v, u);
    }
}
int main()
{
    scanf("%d%d%d", &n, &A, &B);
    for (int i=1; i<n; i++)
    {
        scanf("%d%d", &u1, &v1);
        a[u1].push_back(v1);
        a[v1].push_back(u1);
    }
    dfs(A, -1);
    dfs2(B, -1);

    for (int i=1; i<=n; i++)
        if (disA[i]<disB[i]) ans=max(ans, disB[i]);

    printf("%d", ans-1);
    return 0;
}
/*
9 5 1
1 2
2 3
3 4
4 5
4 6
6 7
7 8
8 9

6

*/