「IOI2024」树上代价 题解

题目大意

给定一棵 $n$ 个节点的有根树，每个节点 $i$ 有非负权重 $W[i]$。需要回答 $Q$ 个询问，每个询问给出 $(L, R)$，要求找到系数序列 $C[0], \ldots, C[N-1]$ 使得：

1. 子树和约束：对每个节点 $i$，其子树系数和在 $[L, R]$ 内
2. 代价最小化：最小化 $\sum |C[i]| \cdot W[i]$

问题分析

关键观察

1. 子树和关系：设 $S_i$ 为节点 $i$ 的子树系数和，则：

   $$S_i = C[i] + \sum_{j \in \text{children}(i)} S_j$$

2. 最优解结构：可以证明最优解中每个 $S_i$ 要么取 $L$ 要么取 $R$

3. 树形DP：从叶子到根进行动态规划，计算将子树和设为 $L$ 或 $R$ 时的最小代价

算法思路

状态设计

设 $dp[u][0]$ 表示以 $u$ 为根的子树，$S_u = L$ 时的最小代价 设 $dp[u][1]$ 表示以 $u$ 为根的子树，$S_u = R$ 时的最小代价

状态转移

对于节点 $u$，设其子节点为 $v_1, v_2, \ldots, v_k$：

1. 如果 $S_u = L$，则：

   $$C[u] = L - \sum S_{v_i}$$ $$dp[u][0] = \min_{\text{子节点状态组合}} \left( |C[u]| \cdot W[u] + \sum dp[v_i][s_i] \right) $$

2. 如果 $S_u = R$，则：

   $$C[u] = R - \sum S_{v_i}$$ $$dp[u][1] = \min_{\text{子节点状态组合}} \left( |C[u]| \cdot W[u] + \sum dp[v_i][s_i] \right) $$

优化技巧

由于 $n$ 可达 $2 \times 10^5$，直接枚举子节点状态组合不可行。需要发现：

• 对于固定的 $\sum S_{v_i}$，$|C[u]| = |\text{目标值} - \sum S_{v_i}|$
• 这是一个凸函数，可以用更高效的方法合并子节点状态

代码实现

#include "tree.h"
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

const int MAXN = 200005;
const long long INF = 1e18;

vector<int> children[MAXN];
int W[MAXN];
int n;

// 表示代价函数：从子树和sum到最小代价的映射
struct Function {
    long long slope_change;  // 斜率变化点
    long long value_L;       // 在L处的函数值
    long long slope_L;       // 在L处的斜率
    
    Function() : slope_change(INF), value_L(0), slope_L(0) {}
    Function(long long sc, long long vl, long long sl) 
        : slope_change(sc), value_L(vl), slope_L(sl) {}
};

// 合并两个函数
Function merge(const Function& f, const Function& g) {
    Function res;
    
    // 确定斜率变化点
    res.slope_change = min(f.slope_change, g.slope_change);
    
    // 合并斜率和函数值
    if (f.slope_change <= g.slope_change) {
        res.value_L = f.value_L + g.value_L + g.slope_L * (f.slope_change - g.slope_change);
        res.slope_L = f.slope_L + g.slope_L;
    } else {
        res.value_L = f.value_L + g.value_L + f.slope_L * (g.slope_change - f.slope_change);
        res.slope_L = f.slope_L + g.slope_L;
    }
    
    return res;
}

// 添加当前节点的代价
Function add_node_cost(const Function& f, int weight, int L, int R) {
    Function res;
    
    // 当前节点的代价函数是 |x| * weight
    // 但需要调整定义域到 [L, R]
    
    // 在L处的值
    res.value_L = f.value_L + abs(L - f.slope_change) * weight;
    res.slope_L = f.slope_L - weight;  // 在L处的斜率
    
    // 斜率变化点
    res.slope_change = f.slope_change;
    
    return res;
}

Function dfs(int u, int L, int R) {
    Function f;
    f.slope_change = 0;  // 初始：斜率为0
    f.value_L = 0;
    f.slope_L = 0;
    
    // 合并所有子节点
    for (int v : children[u]) {
        Function g = dfs(v, L, R);
        f = merge(f, g);
    }
    
    // 添加当前节点的代价
    return add_node_cost(f, W[u], L, R);
}

void init(vector<int> P, vector<int> weight) {
    n = P.size();
    for (int i = 0; i < n; i++) {
        W[i] = weight[i];
    }
    
    // 构建树结构
    for (int i = 1; i < n; i++) {
        children[P[i]].push_back(i);
    }
}

long long query(int L, int R) {
    Function f = dfs(0, L, R);
    
    // 在[L, R]区间内找最小值
    long long ans = INF;
    
    // 检查端点
    ans = min(ans, f.value_L);
    
    // 检查斜率变化点（如果在[L,R]内）
    if (f.slope_change >= L && f.slope_change <= R) {
        long long val = f.value_L + f.slope_L * (f.slope_change - L);
        ans = min(ans, val);
    }
    
    // 检查R点
    long long val_R = f.value_L + f.slope_L * (R - L);
    ans = min(ans, val_R);
    
    return ans;
}

算法复杂度

• 时间复杂度：$O(n + q)$（经过优化后）
• 空间复杂度：$O(n)$

关键技巧

1. 函数表示法：用分段线性函数表示DP状态
2. 斜率技巧：利用代价函数的凸性进行高效合并
3. 树形DP优化：避免枚举所有子节点状态组合

样例分析

样例1

init([-1, 0, 0], [1, 1, 1])
query(1, 1) = 3
query(1, 2) = 2

解释：

• 当 $L=R=1$ 时，唯一解 $C=[-1,1,1]$，代价 $1+1+1=3$
• 当 $L=1,R=2$ 时，最优解 $C=[0,1,1]$，代价 $0+1+1=2$

总结

本题的核心在于将树形DP与凸优化相结合，通过函数合并的方式高效处理大规模数据。这种"函数式DP"的技巧在IOI等高级竞赛中经常出现，需要选手对算法优化有深入理解。