题解 P9096 [PA2020] Sen o podboju

Sol1 · 2023-05-23 22:27:08 · 题解

upd. 修个笔误。

数据随机自然是乱搞。

考虑一个暴力 dp：f_{i,j,k} 表示 i 子树，断了 j 条边，根所在连通块的 a 的和是 k，最小的连通块平方和。

对于边 (u,v)，转移是：

复杂度 O(n^2w^2)，显然过不了。

考虑剪枝，对于 k_1<k_2，如果 f_{i,j,k_1}<f_{i,j,k_2}，那么 k_2 显然没用。

于是我们对每一个 f_{i,j} 开个 vector 存所有有用的 k，每次暴力枚举两个 k 转移，转移完暴力对所有 vector 按 k 排序再暴力删掉所有没用的点。

然后这个算法就直接以最大点不到半秒的优异表现通过了这道题！

复杂度我不会严格分析，不过感性理解的话，假定 dp 数组在树和点权都均匀随机的情况下足够均匀随机，那么根据前缀最大值个数期望（也就是笛卡尔树深度期望），复杂度可以分析为 O(n^2\log^2 w)。

const int N = 305;

struct Edge {
    int to, nxt;
    Edge() {
        nxt = -1;
    }
};
int n, hd[N], siz[N], pnt;
long long a[N];
Edge e[N << 1];
vector <pair <long long, long long> > dp[N][N], tmp[N];

inline void AddEdge(int u, int v) {
    e[++pnt].to = v;
    e[pnt].nxt = hd[u];
    hd[u] = pnt;
}

inline void Read() {
    n = qread();
    for (int i = 1;i <= n;i++) a[i] = qread();
    for (int i = 1;i < n;i++) {
        int u = qread(), v = qread();
        AddEdge(u, v); AddEdge(v, u);
    }
}

inline void Dfs(int u, int fa) {
    siz[u] = 1;
    for (int i = 0;i <= n;i++) dp[u][i].clear();
    dp[u][0].push_back(make_pair(a[u], a[u] * a[u]));
    for (int i = hd[u];~i;i = e[i].nxt) {
        int v = e[i].to;
        if (v != fa) {
            Dfs(v, u);
            for (int i = 0;i <= siz[v];i++) {
                for (int j = 0;j <= siz[u];j++) {
                    for (auto x : dp[v][i]) {
                        for (auto y : dp[u][j]) {
                            tmp[i + j].push_back(make_pair(x.first + y.first, x.second + y.second + 2 * x.first * y.first));
                            tmp[i + j + 1].push_back(make_pair(y.first, x.second + y.second));
                        }
                    }
                }
            }
            siz[u] += siz[v];
            for (int i = 0;i <= siz[u];i++) {
                dp[u][i].clear();
                sort(tmp[i].begin(), tmp[i].end());
                long long mnv = 0x3f3f3f3f3f3f3f3f;
                for (int j = 0;j < tmp[i].size();j++) {
                    if (tmp[i][j].second < mnv) {
                        mnv = tmp[i][j].second;
                        dp[u][i].push_back(tmp[i][j]);
                    }
                }
                tmp[i].clear();
            }
        }
    }
}