Submission #856337

#	Time	Username	Problem	Language	Result	Execution time	Memory
856337		Cyanmond	Chase (CEOI17_chase)	C++17	20 / 100	966 ms	183600 KiB

chase

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define per(i, l, r) for (int i = (r - 1); i >= l; --i)
#define ALL(x) (x).begin(), (x).end()

using i64 = long long;
constexpr i64 inf = 1ll << 60;

void main_() {
    int N, V;
    cin >> N >> V;
    if (V == 0) {
        cout << 0 << endl;
        return;
    }
    vector<i64> P(N);
    for (auto &e : P) cin >> e;
    vector<int> A(N - 1), B(N - 1);
    vector<vector<int>> tree(N);
    rep(i, 0, N - 1) {
        cin >> A[i] >> B[i];
        tree[--A[i]].push_back(--B[i]);
        tree[B[i]].push_back(A[i]);
    }

    i64 ans = 0;
    vector dpu(N, vector(V + 1, 0ll)), dpd(N, vector(V + 1, 0ll));
    auto dfs = [&](auto &&self, const int v, const int p) -> void {
        i64 pSum = 0;
        for (const int t : tree[v]) {
            pSum += P[t];
            if (t == p) continue;
            self(self, t, v);
        }

        // update
        dpu[v][1] = max(dpu[v][1], pSum);
        dpd[v][1] = max(dpd[v][1], pSum - (p == -1 ? 0 : P[p]));
        for (const int t : tree[v]) {
            if (t == p) continue;
            // dpu
            {
                rep(x, 0, V + 1) {
                    dpu[v][x] = max(dpu[v][x], dpu[t][x]);
                    if (x != V) {
                        dpu[v][x + 1] = max(dpu[v][x + 1], dpu[t][x] + pSum - P[t]);
                    }
                }
            }
            // dpd
            {
                rep(x, 0, V + 1) {
                    dpd[v][x] = max(dpd[v][x], dpd[t][x]);
                    if (x != V and p != -1) {
                        dpd[v][x + 1] = max(dpd[v][x + 1], dpd[t][x] + pSum - P[p]);
                    }
                }
            }
        }

        rep(x, 0, V) {
            dpu[v][x + 1] = max(dpu[v][x + 1], dpu[v][x]);
            dpd[v][x + 1] = max(dpd[v][x + 1], dpd[v][x]);
        }

        // merge
        vector dp(V + 1, vector(2, 0ll));
        for (const int t : tree[v]) {
            if (t == p) continue;
            auto ndp = dp;
            rep(x, 0, V + 1) {
                ans = max(ans, dp[x][0] + dpd[t][V - x]);
                ans = max(ans, dp[x][1] + dpu[t][V - x]);
                if (x != V) ans = max(ans, dp[x][1] + dpu[t][V - x - 1] + pSum - P[t]);
            }
            rep(x, 0, V + 1) {
                ndp[x][0] = max(ndp[x][0], dpu[t][x]);
                if (x != V) {
                    ndp[x + 1][0] = max(ndp[x + 1][0], dpu[t][x] + pSum - P[t]);
                }
                ndp[x][1] = max(ndp[x][1], dpd[t][x]);
            }
            dp = move(ndp);
        }
    };
    dfs(dfs, 0, -1);

    /*
    rep(i, 0, N) {
        for (const auto e : dpu[i]) cerr << e << ' ';
        cerr << endl;
        for (const auto e : dpd[i]) cerr << e << ' ';
        cerr << endl;
        cerr << endl;
    }
    */

    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    main_();
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30