洛谷 P3554 分析（别看）

科技起源的小号1

2026-08-28 16:55:13

发布于：天津

1阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最小值

1.2 题目背景、允许、禁止与限制

背景：
有一棵 $n$ 个节点的树，初始时 $1$ 号节点被染黑，其它节点均为白色
允许：
初始时 $B$ 在 $1$ 号节点 $\rightarrow$ 间接地说明了 $1$ 号节点是根节点
每一轮， $A$ 可以先染黑 $k$ 个节点，然后 $B$ 可以走到相邻的任意节点，如果 $B$ 在白色节点则 $B$ 胜，当 $A$ 将所有节点染为黑点时则 $A$ 胜。
求让 $A$ 胜利的最小 $k$

1.3 题目数据范围与猜测

$n \le 3 \times 10^5 \longrightarrow O(n~log~n)$

1.4 一句话概括题意

有一棵树，求一个最小值使得在游戏规则下 $A$ 必胜

2 题目破题推导

2.1 第一步：大拆小，小组大

我们考虑一个节点 $u$ 的“威胁”，也就是在 $u$ 的子树中，还需要额外染黑的节点数量

第一部分：本身欠的（有可能欠负数，也就是不仅可以染孩子，还可以染孩子的子树中需要染黑的）
设 $s(i)$ 代表 $i$ 的子节点数量，则这部分带来的“威胁”值为 $s(u) - k$
第二部分：孩子节点需要补的
设 $f(i)$ 表示 $i$ 的子树中，还需要额外染黑的节点数量， $son(i)$ 代表 $i$ 的所有孩子
则这部分为： $\sum_{v\in son(u)}max(f(v),0)$
为什么是 $max(f(v),0)$ ，而不是 $f(v)$ ？
因为子节点的“威胁”如果是负数，不能用于补充父节点“欠”的，只能补充 $v$ 自己的孩子所欠的

3 模型匹配

这题特别重要的一个转换点：
很多时候，我们看到求一个最小值，就理所当然认为这是dp
但是这道题并没有使用dp求这个最小的k
而是使用了二分答案，树形dp只是一个辅助工具
那么我们的dp定义其实和上面的 $f(i)$ 一样
然后当我们测试完这个 $k$ 后，若 $dp_{root(1)}\le 0$ ，则代表合法

4 最终代码（禁止抄袭，仅用于参考）

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

int n;
const int N = 3e5 + 10;
vector<int> g[N];
int son[N];
int dp[N];
int k;
void check(int u, int fa){
    dp[u] = son[u] - k;
    for (int v : g[u]){
        if (v == fa) continue;
        check(v, u);
        dp[u] += max(dp[v], 1LL * 0);
    }
}
void _dfs(int u, int fa){
    for (int v : g[u]){
        if (v == fa) continue;
        _dfs(v, u);
        son[u]++;
    }
}

signed main(){

    cin >> n;
    for (int i = 1;i < n;i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    _dfs(1, 0);
    int mx = INT_MIN;
    for (int i = 1;i <= n;i++){
        mx = max(mx, son[i]);
    }
    int left = 0, right = mx;
    int ans = 0;
    while(left <= right){
        int mid = (left + right) / 2;
        k = mid;
        memset(dp, 0, sizeof(dp));
        check(1, 0);
        if (dp[1] <= 0){
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    cout << ans;
    
    return 0;
}
// 震惊的是，这题尽管是求最小值，但是求的步骤却没有像大家想的一样用dp，而是用了二分答案
// 树形dp在其中只是起到了一个辅助的作用