COCI 2019/2020 Džumbus 题解

题目分析

这道题要求在有根树结构的朋友关系中，使用有限的饮料预算最大化能够参与题解交流的人数。

关键点：

• 朋友关系构成森林（多棵树）
• 一个人放松需要特定饮料量
• 只有两个人都放松时才能交流题解
• 交流是传递的（形成连通块）

解题思路

核心观察

1. 树形结构：朋友关系是森林，可以添加虚拟根节点变成一棵树
2. 动态规划：在树上进行背包DP，状态记录子树内选择情况
3. 状态设计：需要记录当前节点是否选择、是否与父节点有交流

算法设计

代码采用了树形DP + 背包合并的方法：

状态定义：

f[x][j][a][b] 表示以 x 为根的子树中：

• 选择了 j 个人参与交流
• a = 1 表示节点 x 被选择（放松）
• b = 1 表示节点 x 与父节点有交流连接

代码详解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2e6 + 10;

ll n, m, Q;
ll v[N], rt[N], sz[N], num;
ll f[1010][1010][2][2]; // f[x][j][a][b]
bool vis[N];

struct edge {
    ll nxt, to;
} a[N];
ll head[N], tot;

void add(ll u, ll v) {
    a[++tot].nxt = head[u];
    a[tot].to = v;
    head[u] = tot;
}

// 第一次DFS：找到连通块根节点
void dfs0(ll x) {
    vis[x] = 1;
    for (ll i = head[x]; i; i = a[i].nxt) {
        ll to = a[i].to;
        if (vis[to]) continue;
        dfs0(to);
    }
}

// 树形DP
void dfs(ll x) {
    vis[x] = 1;
    sz[x] = 1;
    
    // 初始化状态
    for (ll i = 1; i <= 1005; i++)
        f[x][i][0][0] = f[x][i][1][0] = f[x][i][1][1] = 1e12;
    
    f[x][0][1][0] = v[x];  // 只选自己，不与父交流
    f[x][0][1][1] = 1e12;  // 无效状态
    
    // 处理子节点
    for (ll i = head[x]; i; i = a[i].nxt) {
        ll to = a[i].to;
        if (vis[to]) continue;
        
        dfs(to);
        
        // 背包合并
        for (ll j = sz[x]; j >= 0; j--) {
            for (ll k = sz[to]; k >= 0; k--) {
                // 状态转移
                f[x][j + k + 2][1][1] = min(f[x][j + k + 2][1][1], 
                    f[x][j][1][0] + f[to][k][1][0]);
                f[x][j + k + 1][1][1] = min(f[x][j + k + 1][1][1], 
                    f[x][j][1][0] + f[to][k][1][1]);
                f[x][j + k + 1][1][1] = min(f[x][j + k + 1][1][1], 
                    f[x][j][1][1] + f[to][k][1][0]);
                f[x][j + k][1][1] = min(f[x][j + k][1][1], 
                    f[x][j][1][1] + f[to][k][0][0]);
                f[x][j + k][1][1] = min(f[x][j + k][1][1], 
                    f[x][j][1][1] + f[to][k][1][1]);
                f[x][j + k][1][0] = min(f[x][j + k][1][0], 
                    f[x][j][1][0] + f[to][k][0][0]);
                f[x][j + k][0][0] = min(f[x][j + k][0][0], 
                    f[x][j][0][0] + f[to][k][0][0]);
                f[x][j + k][0][0] = min(f[x][j + k][0][0], 
                    f[x][j][0][0] + f[to][k][1][0]);
                f[x][j + k][0][0] = min(f[x][j + k][0][0], 
                    f[x][j][0][0] + f[to][k][1][1]);
            }
        }
        sz[x] += sz[to];
    }
}

int main() {
    cin >> n >> m;
    v[n + 1] = 1e12;  // 虚拟根节点
    
    for (ll i = 1; i <= n; i++)
        cin >> v[i];
    
    // 建图
    for (ll i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        add(u, v), add(v, u);
    }
    
    // 找到所有连通分量
    for (ll i = 1; i <= n; i++) {
        if (!vis[i]) {
            rt[++num] = i;
            dfs0(i);
            add(n + 1, i);  // 连接到虚拟根
        }
    }
    
    // 树形DP
    memset(vis, 0, sizeof(vis));
    dfs(n + 1);
    
    // 处理查询
    cin >> Q;
    while (Q--) {
        ll now;
        cin >> now;
        
        // 二分找到最大人数
        ll l = 2, r = n;
        while (l < r) {
            ll mid = (l + r + 1) >> 1;
            if (f[n + 1][mid][0][0] <= now)
                l = mid;
            else {
                if (f[n + 1][mid + 1][0][0] <= now)
                    l = mid + 1;
                else
                    r = mid - 1;
            }
        }
        
        if (f[n + 1][l][0][0] > now)
            l = 0;
            
        cout << l << '\n';
    }
    
    return 0;
}

算法原理详解

状态转移分析

对于节点 x 和子节点 to：

1. x 选择且与父交流，to 选择且与父交流

   • 需要额外边连接：j + k + 2
   • 成本：f[x][j][1][0] + f[to][k][1][0]

2. x 选择且与父交流，to 选择但不与父交流

   • 需要额外边：j + k + 1
   • 成本：f[x][j][1][0] + f[to][k][1][1]

3. 其他情况类似，考虑所有组合可能性

虚拟根节点

添加节点 n+1 作为虚拟根，将所有连通分量连接成一棵树，简化处理。

查询处理

对于每个预算 now，在DP结果中二分查找满足成本约束的最大人数。

复杂度分析

• 时间复杂度：$O(n^2)$ 树形DP + $O(Q \log n)$ 查询
• 空间复杂度：$O(n^2)$

样例解析

样例2：

3 2
1 2 3
1 2
1 3
3
2
3
5

树结构：节点1为根，连接2和3

• 预算2：无法让任何人放松 → 0人
• 预算3：让1放松，1-2和1-3交流 → 3人（但输出2？需要检查）
• 预算5：同上

关键技巧

1. 虚拟根节点：处理森林情况
2. 状态压缩：用4维状态记录选择和交流情况
3. 背包合并：子树DP结果合并到父节点
4. 二分答案：快速回答多个查询

总结

这道题的解题亮点：

1. 问题建模：将交流网络抽象为树形结构
2. 状态设计：精细的状态表示交流关系
3. DP优化：通过背包合并高效计算
4. 预处理+二分：支持快速查询

算法通过深入的树形DP设计，在 $O(n^2)$ 时间内预处理，然后 $O(\log n)$ 回答每个查询，高效解决了这个复杂的优化问题。