제출 #1111352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1111352		Zero_OP	Chase (CEOI17_chase)	C++14	40 / 100	4059 ms	177284 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 MAX_N = 1e5 + 5;
const int MAX_K = 100 + 5;

int N, K, p[MAX_N];
long long sum_neighbor[MAX_N];
vector<int> adj[MAX_N];
long long f[MAX_N][MAX_K], g[MAX_N][MAX_K], ans;

//f[u][i] = if p[u] > 0
//g[u][i] = if p[u] = 0

void dfs(int u, int pre){
    for(int v : adj[u]) if(v != pre){
        for(int i = 1; i <= K; ++i){
            f[v][i] = max(f[u][i - 1], g[u][i - 1]) - p[u] + sum_neighbor[v];
            g[v][i] = max(f[u][i], g[u][i]);
        }

        dfs(v, u);
    }

    maximize(ans, max(f[u][K], g[u][K]));
}

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

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

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

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

    for(int i = 0; i < N; ++i){
        for(int u = 0; u < N; ++u) for(int k = 0; k < K; ++k) f[u][k] = g[u][k] = 0;
        for(int k = 1; k <= K; ++k) f[i][k] = sum_neighbor[i];
        dfs(i, -1);
    }
    cout << ans << '\n';

    return 0;
}

/*

12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12

10 2
1 9 1 9 9 1 9 1 1 1
1 2
2 3
3 4
3 5
2 6
1 7
7 8
8 9
7 10


*/

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