自动搬运

查看原文

来自洛谷，原作者为

	Sol1 博客：sol1.netlify.app

搬运于2025-08-24 22:45:19，当前版本为作者最后更新于2023-05-23 22:27:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

upd. 修个笔误。

数据随机自然是乱搞。

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

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

• $f_{u,x,y}+f_{v,p,q}+2yq\rightarrow f_{u,x+p,y+q}'$（不断 $u,v$ 边）
• $f_{u,x,y}+f_{v,p,q}\rightarrow f_{u,x+p+1,y}'$（断 $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();
            }
        }
    }
}