题解：CF1249F Maximum Weight Subset

· · 题解

总的来说不太难，水一发。

思路

设 f_{u,i} 表示：u 子树内选点，两两距离 >k，且子树内所有选中的点到 u 的距离都至少为 i 的最大权值和。

合并儿子 v 到 u 时， 两部分选中的点之间距离至少为 i+j+1，要满足 >k，需 i+j+1>k，即 j\ge k-i。

合并后最近点到 u 的下界变为 \min(i,j+1)。
用临时数组 d 避免重复转移：

d_{\min(i,j+1)} = \max(d_{\min(i,j+1)},\ f_{u,i} + f_{v,j})

其中 j\ge\max(0,k-i)。枚举完所有 i,j 后将 d 赋回 f_u。

代码


#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, k, f[205][205], a[205], d[205];
vector<int> g[205];
void merge(int u, int v) {
    for (int i = 0; i <= n; i++) {
        d[i] = f[u][i];
    }
    for (int i = 0; i <= n; i++) {
        for (int j = max(0ll, k - i); j <= n; j++) {
            d[min(i, j + 1)] = max(d[min(i, j + 1)], f[u][i] + f[v][j]);
        }
    }
    for (int i = 0; i <= n; i++) {
        f[u][i] = d[i];
    }
    return;
}
void dfs(int u, int p) {
    f[u][0] = a[u];
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v != p) {
            dfs(v, u);
            merge(u, v);
        }
    }
    return;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1, x, y; i < n; i++) {
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1, 0);
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        ans = max(ans, f[1][i]);
    }
    cout << ans << endl;
    return 0;
}
``