写在前面

来给 zrm 大佬的题写一篇题解。

这题代码实现难度不高，但是比较锻炼思维，而且应该有不少种解法。着实是一道质量很高的题目。

算法思路

首先呢，显然当小 Z 向当前节点的一棵子树走去时，这棵子树上的 youyou 会与小 Z 的距离减 \(2\) 或者减 \(1\)（减 \(1\) 当且仅当小 Z 的射程与 youyou 的距离为 \(1\)）。而其余节点上的 youyou 与小 Z 的相对距离不会发生变化。

其次，小 Z 在一棵子树上花的所有时间，只和这棵子树上最深的有 youyou 的节点有关。

所以，小 Z 只需要去迎上离出发点最深的 youyou，然后在消灭这只 youyou 后再去迎离当前节点最深的 youyou，其余的 youyou 一定能在这个过程中被全部消灭。

用类似于求树的直径的方法，通过 dfs 找到最深 youyou 的深度、最远的两只 youyou 的距离，那么消灭第一只 youyou 后，这时最深的 youyou 深度就是最远距离 \(-\) 第一只 youyou 的深度。

时间复杂度 \(\Theta(n)\)。

Tips

• 算出两次需要移动的距离来之后直接让距离减去射程 \(k\) 可以让思考简单一些。（下文的距离指减去射程后的距离）

• 处理好两次移动距离的奇偶性。如果是奇数，距离为 \(1\) 后直接原地等一回合就好，这样答案不会变劣。并且将次远的 youyou 的距离减 \(1\)。

• 注意特判一下一回合就能消灭全部 youyou 的情况和次远的 youyou 在射程范围内的情况。

• 注意一回合是先射击在移动，因此消灭最后的 youyou 的回合是一个额外的回合。

Code

#include<bits/stdc++.h>
using namespace std;

const int Maxn = 4e5 + 5;

int n, m, x, y, k, T, ans;

struct e {
    int to, next;
} b[Maxn << 1];
int head[Maxn], cnt;

bool vis[Maxn];
bool yy[Maxn];

int dep1st, id1st, dep2nd, id2nd;
int Maxdep, Maxid;

void add(int u, int v)
{
    cnt++;
    b[cnt].next = head[u];
    b[cnt].to = v;
    head[u] = cnt;
}

inline int read()
{
    int f = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
    return f * w;
}

void dfs(int t, int dep)
{
    if(vis[t]) return;
    vis[t] = 1;
    if((dep > Maxdep) && yy[t])
    {
        Maxdep = dep;
        Maxid = t;
    }
    for(int i = head[t]; i; i = b[i].next)
    {
        int tto = b[i].to;
        if(vis[tto]) continue;
        dfs(tto, dep + 1);
    }
}

int main()
{
    n = read() - 1;
    while(n--)
    {
        x = read(); y = read();
        add(x, y); add(y, x);
    }
    m = read();
    while(m--)
    {
        x = read();
        yy[x] = 1;
    }
    k = read(); T = read();
    dfs(T, 0);
    dep1st = Maxdep; id1st = Maxid;
    memset(vis, 0, sizeof(vis));
    Maxdep = 0; Maxid = 0;
    dfs(id1st, 0);
    dep2nd = Maxdep - dep1st; id2nd = Maxid;
    dep1st -= k; dep2nd -= k;
    if((dep1st) <= 0 && (dep2nd <= 0))
    {
        printf("%d", 1);
    }
    else if((dep2nd <= 0))
    {
        printf("%d", (dep1st/2) + (int)(dep1st & 1) + 1);
    }
    else
    {
        if(dep1st & 1)
        {
            dep2nd--;
            ans++;
        }
        printf("%d", ans + (dep1st/2) + (dep2nd/2) + (int)(dep2nd & 1) + 1);
    }
    return 0;
}