题目理解与建模

问题重述

我们有一棵 n 个节点的树，根节点为 1（首都）。除了根节点外，其他节点都没有凯旋门。每天我们可以派建筑队在任意节点建造凯旋门，每个建筑队每天只能在一个节点工作。国王从根节点出发，每天移动到相邻节点，访问顺序未知。我们需要保证国王第一次访问某个节点时，该节点已有凯旋门。

目标：最小化建筑队数量。

关键观察

1. 树的结构：由于是树，国王的移动路径是唯一的（无环）
2. 访问顺序的不确定性：我们不知道国王的具体访问顺序，但知道是深度优先的遍历
3. 建造时机：必须在国王第一次访问节点前建好凯旋门

算法思路

核心思想：二分答案 + 树形DP验证

1. 二分答案

• 下界：l = 0（显然至少需要1个队伍）
• 上界：r = 最大子节点数（最坏情况需要处理所有直接子节点）
• 我们二分搜索最小的建筑队数量 k，使得能够满足要求

2. 树形DP验证

对于给定的 k，我们定义状态：

• siz[u]：节点 u 的子节点数量
• f[u]：以 u 为根的子树中，还需要额外处理的节点数

状态转移：

f[u] = siz[u] - k + ∑ max(0, f[v])  // v是u的子节点

状态转移的解释：

• siz[u] - k：节点 u 有 siz[u] 个子节点，每天可以处理 k 个，剩余的需要父节点帮忙
• ∑ max(0, f[v])：子节点 v 如果还有未处理完的节点 (f[v] > 0)，需要父节点 u 来帮忙处理

验证条件：如果 f[1] <= 0，说明根节点能够处理完所有需求，k 是可行的。

代码详细解析

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

const int maxn = 3e5 + 5;
int n;
vector<int> e[maxn];  // 邻接表存储树
int siz[maxn], ans;   // siz[u]: u的子节点数, ans: 记录最大子节点数的节点

// 第一次DFS：计算每个节点的子节点数，并找到最大子节点数的节点
void dfs(int u, int fa) {
    for (auto v : e[u]) {
        if (v == fa) continue;
        ++siz[u];      // 统计直接子节点数量
        dfs(v, u);
    }
    if (siz[u] > siz[ans]) ans = u;  // 更新最大子节点数的节点
}

int f[maxn], t;  // f[u]: DP数组, t: 当前尝试的建筑队数量

// 第二次DFS：树形DP验证当前建筑队数量t是否可行
inline void dfs1(int u, int fa) {
    f[u] = siz[u] - t;  // 初始值：子节点数 - 每天能处理的节点数
    
    for (int v : e[u]) {
        if (v == fa) continue;
        dfs1(v, u);
        f[u] += max(0, f[v]);  // 如果子节点有未处理完的，父节点需要帮忙
    }
}

// 检查函数：验证k个建筑队是否足够
inline bool check(int x) {
    t = x;
    dfs1(1, 0);
    return f[1] <= 0;  // 根节点的需求<=0表示可行
}

int main() {
    read(n);
    
    // 建图
    for (int i = 1; i < n; i++) {
        int u, v;
        read(u), read(v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    
    // 第一次DFS：预处理
    dfs(1, 0);
    
    // 二分答案
    int l = 0, r = siz[ans], ans = siz[ans];
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;  // 尝试更小的值
        } else {
            l = mid + 1;  // 需要更多的建筑队
        }
    }
    
    cout << ans << '\n';
    return 0;
}

样例分析

以题目样例为例：

7
1 2
1 3
2 5
2 6
7 2
4 1

树结构：

    1
   /|\
  2 3 4
 /|\
5 6 7

• siz[1] = 3（子节点：2,3,4）
• siz[2] = 3（子节点：5,6,7）
• 其他节点 siz[u] = 0

二分过程：

• 尝试 k = 2：f[1] > 0，不可行
• 尝试 k = 3：f[1] <= 0，可行
• 最终答案：3

算法正确性证明

为什么这样设计DP状态？

考虑国王的访问过程：当国王在节点 u 时，他下一步可能访问 u 的任意子节点。为了确保国王访问子节点时该节点已有凯旋门，我们需要：

1. 在国王到达 u 之前，处理好 u 的所有子节点
2. 如果某个子节点 v 的子树很大，可能需要提前处理

我们的DP状态 f[u] 正好反映了这种"提前处理"的需求。

为什么验证条件是 f[1] <= 0？

• f[1] > 0：表示根节点还有未处理完的需求，需要更多建筑队
• f[1] <= 0：表示根节点能够处理完所有需求，当前建筑队数量足够

时间复杂度分析

• 建图：O(n)
• 第一次DFS：O(n)
• 二分答案：O(log n)
• 每次验证：O(n)
• 总复杂度：O(n log n)，对于 n ≤ 300000 完全可行

学习要点

1. 二分答案的应用场景：当问题可以转化为"判断某个值是否可行"时，考虑二分
2. 树形DP的设计：根据树的结构设计状态，利用DFS进行状态转移
3. 贪心思想的融入：在状态转移时，只考虑需要帮助的子节点 (max(0, f[v]))
4. 问题建模能力：将实际问题的约束转化为数学模型

这道题很好地结合了二分答案和树形DP，是学习这两种重要算法的优秀例题。