Submission #1111505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111505		Zero_OP	Chase (CEOI17_chase)	C++14	100 / 100	221 ms	227668 KiB

chase

#include <bits/stdc++.h>

using namespace std;

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b) return a = b, true;
        return false;
    }

const int MAXN = 1e5 + 1;
const int MAXK = 105;

long long dp_s[MAXN][MAXK], dp_t[MAXN][MAXK]; //is the start, if choose u, used breadcumbs, at subtree u

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    int N, K;
    cin >> N >> K;
    vector<int> a(N);
    for(int i = 0; i < N; ++i) cin >> a[i];
    vector<vector<int>> adj(N);
    vector<long long> sum_neighbor(N);
    for(int i = 1; i < N; ++i){
        int u, v; cin >> u >> v;
        --u, --v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
        sum_neighbor[u] += a[v];
        sum_neighbor[v] += a[u];
    }

    if(K == 0){
        cout << 0 << '\n';
        return 0;
    }

    long long ans = 0;

    function<void(int, int)> dfs = [&](int u, int p){
        dp_s[u][1] = sum_neighbor[u];
        long long f = (p != -1 ? a[p] : 0);

        vector<long long> save_s(K + 1), save_t(K + 1);
        for(int v : adj[u]) if(v != p){
            dfs(v, u);
            for(int i = 1; i <= K; ++i){
                save_s[i] = max(dp_s[v][i], dp_s[v][i - 1] + sum_neighbor[u] - a[v]);
                save_t[i] = max(dp_t[v][i], dp_t[v][i - 1] + sum_neighbor[v] - a[u]);

                if(K - i > 0){
                    maximize(ans, dp_s[u][K - i] + save_t[i]);
                    maximize(ans, dp_t[u][K - i] + save_s[i]);
                }
            }

            for(int i = 1; i <= K; ++i){
                maximize(dp_s[u][i], save_s[i]);
                maximize(dp_t[u][i], save_t[i]);
            }
        }

        maximize(ans, dp_s[u][K]);
    };

    dfs(0, -1);
    cout << ans << '\n';

    return 0;
}

Compilation message (stderr)

chase.cpp: In lambda function:
chase.cpp:43:19: warning: unused variable 'f' [-Wunused-variable]
   43 |         long long f = (p != -1 ? a[p] : 0);
      |                   ^

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