제출 #1289226

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289226		ninhtay	Chase (CEOI17_chase)	C++20	0 / 100	521 ms	178904 KiB

chase

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

const int MAXN = 100005;
const int MAXV = 105;
long long p[MAXN], val[MAXN];
vector<int> adj[MAXN];
long long f[MAXN][MAXV][2];
int n, V;

void dfs(int u, int par) {
    f[u][0][0] = 0;
    f[u][1][1] = val[u];
    int sz = 1;

    for (int v : adj[u]) if (v != par) {
        dfs(v, u);

        static long long new0[MAXV], new1[MAXV];
        for (int i = 0; i <= V; i++) new0[i] = new1[i] = -1e18;

        for (int ku = 0; ku <= min(V, sz); ku++) {
            if (f[u][ku][0] < -1e17 && f[u][ku][1] < -1e17) continue;
            for (int kv = 0; kv + ku <= V; kv++) {
                
                if (f[u][ku][0] > -1e17) {
                    long long bestv = max(f[v][kv][0], f[v][kv][1]);
                    new0[ku + kv] = max(new0[ku + kv],
                                        f[u][ku][0] + bestv);
                }
                
                if (f[u][ku][1] > -1e17) {
                    new1[ku + kv] = max(new1[ku + kv],
                                        f[u][ku][1] + f[v][kv][0]);
                }
            }
        }

        for (int i = 0; i <= V; i++) {
            f[u][i][0] = new0[i];
            f[u][i][1] = new1[i];
        }
        sz = min(V, sz + V);
    }
}

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

    cin >> n >> V;
    for (int i = 1; i <= n; i++) cin >> p[i];

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

    
    for (int u = 1; u <= n; u++) {
        long long s = 0;
        for (int v : adj[u]) s += p[v];
        val[u] = s;
    }


    for (int i = 1; i <= n; i++)
        for (int k = 0; k <= V; k++)
            f[i][k][0] = f[i][k][1] = -1e18;

    dfs(1, 0);

    long long ans = 0;
    for (int k = 0; k <= V; k++)
        ans = max({ans, f[1][k][0], f[1][k][1]});

    cout << ans << "\n";
    return 0;
}

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