Submission #468554

#	Time	Username	Problem	Language	Result	Execution time	Memory
468554		idk321	Chase (CEOI17_chase)	C++17	70 / 100	534 ms	170300 KiB

chase

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100005;
const int V = 101;
int p[N];
int n, v;
vector<int> adj[N];
ll dp[N][2][V];

void dfs(int node, int par) {

    for (int next : adj[node]) {
        if (next == par) continue;
        dp[node][1][1] += p[next];
        dfs(next, node);
    }
    for (int next : adj[node]) {
        if (next == par) continue;
        for (int i = 0; i <= v; i++) {
            dp[node][0][i] = max(dp[node][0][i], dp[node][0][0] + dp[next][0][i]);
            dp[node][0][i] = max(dp[node][0][i], dp[node][0][0] + dp[next][1][i]);
            if (i != v) {
                dp[node][1][i + 1] = max(dp[node][1][i + 1], dp[node][1][1] + dp[next][0][i]);
                dp[node][1][i + 1] = max(dp[node][1][i + 1], dp[node][1][1] + dp[next][1][i]);
            }
        }
    }
}

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

    cin >> n >> v;
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    ll res = 0;
    for (int root = 1; root <= (n <= 1000 ? n : 1); root++) {
        for (int a = 0; a <= n; a++) for (int b = 0; b < 2; b++) for (int c = 0; c <= v; c++) dp[a][b][c] = 0;
        dfs(root, -1);
        ll sum = 0;
        for (int i = 1; i <= n; i++) sum += p[i];
        for (int i = 0; i <= v; i++) {
            for (int j = 0; j < 2; j++) res = max(res, dp[root][j][i]);
        }
    }


    cout << res << "\n";
}

/*
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
*/

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