「POI 2023/2024 R3」Wyjścia ewakuacyjne 题解

题目分析

这是一个在树形结构上设置紧急出口的最优化问题。大楼的走廊形成一棵树，每个房间有初始人数，每条走廊有通行容量限制。我们需要在尽量少的房间设置紧急出口，使得所有人都能沿着箭头指引安全疏散。

核心思路

使用树形DP的思想，自底向上处理每个子树，维护一个状态值 f[x] 来表示当前子树的"人流状况"。

状态定义

f[x] 表示以节点 x 为根的子树中：

• 如果 f[x] >= 0：表示该子树需要向上传递的总人数
• 如果 f[x] < 0：表示该子树还能容纳的人数（剩余容量）

状态转移

在DFS过程中，对于每个节点 x：

1. 初始化：f[x] = a[x]（当前房间的初始人数）

2. 处理子节点：

   • 对于每个子节点 v：
     • 如果 f[v] >= 0：说明子节点 v 的子树需要向上传递人流，累加到当前节点
     • 如果 f[v] < 0：说明子节点 v 的子树还有剩余容量，记录最大剩余容量

3. 决策判断：

   • 如果当前总人数 <= 最大剩余容量：可以全部被容纳，更新为负值表示剩余容量
   • 如果当前总人数 > 父边容量：必须在当前节点设置出口，并更新状态

算法详解

void dfs(int x, int fa, int fw) {
    f[x] = a[x];  // 初始化为当前房间人数
    int mx = 0;   // 记录子树的剩余容量（取最大值）

    // 遍历所有子节点
    for (auto [v, w] : g[x]) {
        if (v == fa) continue;
        
        dfs(v, x, w);  // 递归处理子树
        
        if (f[v] >= 0) 
            f[x] += f[v];  // 子树需要传递人数，累加
        else 
            mx = max(mx, -f[v]);  // 子树有剩余容量，记录最大值
    }

    // 关键决策逻辑
    if (f[x] <= mx) {
        // 情况1：总人数可以被剩余容量完全容纳
        f[x] = -min(fw, mx - f[x]);
    } else if (f[x] > fw) {
        // 情况2：总人数超过父边容量，必须设置出口
        f[x] = -fw;  // 设置出口后，剩余容量为父边容量
        ans++;       // 出口数量+1
    }
    // 情况3：总人数在剩余容量和父边容量之间，直接向上传递
}

三种情况举例说明

情况1：可以被子树容量容纳

节点x：人数=5
子节点1：剩余容量=3
子节点2：剩余容量=4
总人数5 <= 最大容量4 → 可以被容纳

情况2：必须设置出口

节点x：人数=10
父边容量=8
10 > 8 → 必须设置出口

情况3：直接向上传递

节点x：人数=6
父边容量=10，子树无剩余容量
6 <= 10 → 直接向上传递6人

复杂度分析

• 时间复杂度：$O(n)$，每个节点只被访问一次
• 空间复杂度：$O(n)$，存储树结构和DP状态

代码实现细节

1. 使用 signed main()：因为定义了 #define int long long
2. 输入输出优化：ios::sync_with_stdio(false); cin.tie(0);
3. 树存储：使用邻接表 vector<pair<int, int>> g[N]
4. 边界处理：根节点的父边容量为0，不影响结果

学习要点

1. 树形DP的经典应用：自底向上传递信息
2. 状态设计的技巧：用正负值表示不同含义
3. 贪心思想的运用：在决策时选择最优方案
4. 边界情况的处理：容量限制和人数累加的关系

这个解法巧妙地将复杂的最优化问题转化为树上的状态转移问题，通过合理的状态设计和决策逻辑，高效地解决了问题。