题解 CF2207D 【Boxed Like a Fish】

Leasier · 2026-03-09 17:00:28 · 题解

赛时改题面的部分道尽一切（确信）

首先不妨思考几个 naive 的情况：

• 当 v 为叶子，答案为 YES。
• 当 v 存在两个儿子，使得 v 沿着这两个儿子的方向离最近的叶子距离 \leq k，答案为 YES……吗？

注意到赛时改题面时加了一句话：but he doesn't have to do it immediately；这使我们重新审视上面这种看似简单的情况：

• 刚刚的结论基于这一假定：Snorlax 首步必须要阻断一条边。
• 但事实上这样并非最优：
• (1) 考虑原树为一条长为 5 的链 1 - 2 - 3 - 4 - 5 的情况，设 k = 2, v = 3。
• (2) 考虑 Snorlax 首步先不操作、而是观察 Cyndaquil 会走哪边；不妨设 Cyndaquil 第一步走了 3 \rightarrow 2。
• (3) 此时 Snorlax 显然需要阻断 1 - 2 边，则计时器回到 2，且 Cyndaquil 被迫向右前进。
• (4) Cyndaquil 停在原地显然不优，于是他接下来两步走了 2 \to 3 \to 4。
• (5) 此时计时器归零，Snorlax 出手阻断 4 - 5 边，Cyndaquil 再次被迫折返。
• 此后博弈将陷入僵局，Cyndaquil 无法抵达一个叶子，答案为 NO。

考虑将上面这种链的情况稍加一般化：

• 考虑依照初始状态定义我们要讨论的“标准状态”：Cyndaquil 处在点 u，且计时器为 0。
• 现在从 u 出发有 k 个方向，不考虑阻断时沿着这些方向至少走 d_1, \cdots, d_k 步即可到达一个叶子。
• Snorlax 首先不操作，等 Cyndaquil 沿着方向 i 走 d_i - 1 步，然后出手阻断最后一步。
• 注：这里 Cyndaquil 不走显然是不优的，因为这会导致僵局。
• 此时计时器回到 k，Cyndaquil 则是立刻调头回到 u，并尝试沿着方向 j \neq i 走 d_j 步到达一个叶子。
• 若 d_i + d_j - 1 \leq k，答案为 YES；否则，答案为 NO。
• 显然，取 d_i, d_j 分别为 d_1, \cdots, d_k 中最小及次小者即可。

但这样做显然是有问题的：

• 要是方向 i 里还有分叉，那就算 Snorlax 出手阻断了最后一步，那我也未必要折返到 u 才能继续走啊？

不妨考虑这种最基本的反例：

• 其中 u - \text{lca} - p_1 为 d_i 所指示的路径，u - q 为 d_j 所指示的路径。
• 若 Cyndaquil 在离 p_1 一步之遥的时候折返到 \text{lca} 处、并向下到达 p_2，则 \text{lca} 恰好满足上述条件。
• 也就是说，此时只要能到达“在 \text{lca} 且计时器为 0 的状态”，答案就为 YES。
• 同时，注意到“计时器为 0”的要求可以去除：因为 Cyndaquil 总能等到计时器归零。
• 也就是说，本例中的 \text{lca} 实际上可以与叶子等同：它们都是“必胜点”。只要采取这一视角，反例自解。

借助这个反例，我们得以扩展上面的想法：

• 设 dp_u 表示从 u 到 u 子树内最近的必胜点的距离。
• (1) 当 u 为叶子，dp_u = 0。
• (2) 当 u 不为叶子，令 p, q 分别为 \{dp_x + 1 \mid x \in \text{son}_u\} 的最大值和次大值（不存在则令之为 +\infty）。
• (i) 若 p + q - 1 \leq k，令 dp_u = 0。
• (ii) 否则，令 dp_u = p。
• 若 dp_v = 0，答案为 YES；否则，答案为 NO。

时间复杂度为 O(\sum n)。

代码：

#include <stdio.h>

struct Edge {
    int nxt;
    int end;
};

int cnt;
int head[500001], dp[500001];
Edge edge[999999];

void init(int n){
    cnt = 0;
    for (int i = 1; i <= n; i++){
        head[i] = 0;
    }
}

int read(){
    int ans = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9'){
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9'){
        ans = ans * 10 + (ch ^ 48);
        ch = getchar();
    }
    return ans;
}

void add_edge(int start, int end){
    cnt++;
    edge[cnt].nxt = head[start];
    head[start] = cnt;
    edge[cnt].end = end;
}

void dfs(int u, int father, int k){
    int cmin = 2e9;
    bool leaf = true;
    dp[u] = 2e9;
    for (int i = head[u]; i != 0; i = edge[i].nxt){
        int x = edge[i].end;
        if (x != father){
            leaf = false;
            dfs(x, u, k);
            if (dp[u] > dp[x] + 1){
                cmin = dp[u];
                dp[u] = dp[x] + 1;
            } else if (cmin > dp[x] + 1){
                cmin = dp[x] + 1;
            }
        }
    }
    if (leaf || dp[u] + cmin - 1 <= k) dp[u] = 0;
}

void solve(){
    int n = read(), k = read(), v = read();
    init(n);
    for (int i = 1; i < n; i++){
        int a = read(), b = read();
        add_edge(a, b);
        add_edge(b, a);
    }
    dfs(v, 0, k);
    if (dp[v] == 0){
        printf("YES\n");
    } else {
        printf("NO\n");
    }
}

int main(){
    int t = read();
    for (int cas = 1; cas <= t; cas++){
        solve();
    }
    return 0;
}