「PA 2020」Sen o podboju 题解

算法思路

本题使用树形动态规划结合凸包优化来解决树划分问题。核心思想是通过维护每个节点的状态集合来找到最优的划分方案。

关键观察

1. 问题转化

将树划分为 $k$ 个连通块，最小化 $\sum S_i^2$，其中 $S_i$ 是第 $i$ 个连通块的军事系数和。

2. 状态设计

对于每个节点 $x$ 和划分块数 $i$，维护一个集合 $f[x][i]$，其中每个元素是 $(代价, 和)$ 对，表示在 $x$ 的子树中划分 $i$ 块的最小代价和当前连通块的和。

代码解析

数据结构定义

vector<pll> f[N][N], h[N];  // f[x][i]: 节点x子树划分i块的状态集合

状态合并函数

vector<pll> merge(vector<pll> a, vector<pll> b) {
    vector<pll> c(a.size() + b.size());
    merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
    vector<pll> d;
    
    // 维护凸包：去除被支配的状态
    for (auto [x, y] : c) {
        if (d.size() && y >= d.back().second)
            continue;
        d.push_back({x, y});
    }
    return d;
}

状态转移函数

vector<pll> add(vector<pll> a, vector<pll> b) {
    vector<pll> ret;
    
    for (auto [sa, da] : a) {
        auto c = b;
        // 状态转移：合并两个子树
        for (auto &[sc, dc] : c)
            sc += sa + dc * da * 2, dc += da;
        
        sort(c.begin(), c.end());
        ret = merge(ret, c);
    }
    return ret;
}

树形DP核心

void dfs(int x, int fa) {
    // 初始化：当前节点单独一个块
    sz[x] = 0;
    f[x][0] = {{1ll * a[x] * a[x], a[x]}};
    
    // 合并子树
    for (auto v : g[x]) {
        if (v == fa) continue;
        dfs(v, x);
        
        // 合并当前状态和子树状态
        for (int i = 0; i <= sz[x] + sz[v]; i++)
            h[i].clear();
            
        for (int i = 0; i <= sz[x]; i++)
            for (int j = 0; j <= sz[v]; j++)
                h[i + j] = merge(h[i + j], add(f[x][i], f[v][j]));
        
        sz[x] += sz[v];
        for (int i = 0; i <= sz[x]; i++)
            f[x][i].swap(h[i]);
    }
    
    // 考虑将当前节点作为新块的起点
    ++sz[x];
    for (int i = sz[x]; i >= 1; i--) {
        ll mn = 1e18;
        for (auto &[a, b] : f[x][i - 1])
            mn = min(mn, a);
        f[x][i] = merge(f[x][i], {{mn, 0}});
    }
}

算法正确性

状态转移方程

设 $f[x][i]$ 表示在 $x$ 的子树中划分 $i$ 块的最小代价集合。

转移考虑两种情形：

1. 不分割：当前节点与子树在同一块

   $$cost_{new} = cost_x + cost_v + 2 \cdot sum_x \cdot sum_v $$$$sum_{new} = sum_x + sum_v$$

2. 分割：当前节点与子树在不同块 直接相加代价

凸包优化

通过维护 $(代价, 和)$ 的凸包，去除被支配的状态，减少状态数量。

复杂度分析

• 时间复杂度：$O(t \cdot n^3)$ 或 $O(t \cdot n^2 \cdot \text{状态数})$
• 空间复杂度：$O(n^2 \cdot \text{状态数})$