제출 #962221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
962221		LucaIlie	Chase (CEOI17_chase)	C++17	100 / 100	579 ms	493352 KiB

chase

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
const int MAX_K = 100;
int k;
long long a[MAX_N + 1], b[MAX_N + 1];
long long dpUp[MAX_N + 1][MAX_K + 1][3], dpDown[MAX_N + 1][MAX_K + 1][3];
vector<int> adj[MAX_N + 1];

long long maxCost = 0;

void dfs( int u, int p ) {
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        dfs( v, u );
    }

    for ( int x = 0; x <= k; x++ )
        dpUp[u][x][0] = dpUp[u][x][1] = dpUp[u][x][2] = dpDown[u][x][0] = dpDown[u][x][1] = dpDown[u][x][2] = 0;
    for ( int x = 1; x <= k; x++ )
        dpUp[u][x][0] = dpDown[u][x][0] = b[u];

    for ( int v: adj[u] ) {
        if ( v == p )
            continue;

        for ( int x = 1; x <= k - 1; x++ ) {
            maxCost = max( maxCost, dpUp[u][x][0] + dpDown[v][k - x][0] - a[u] );
            maxCost = max( maxCost, dpUp[u][x][0] + dpDown[v][k - x][1] );
            maxCost = max( maxCost, dpUp[u][x][0] + dpDown[v][k - x][2] );
            maxCost = max( maxCost, dpUp[u][x][1] + dpDown[v][k - x][0] - a[u] );
            maxCost = max( maxCost, dpUp[u][x][2] + dpDown[v][k - x][0] - a[u] );
            maxCost = max( maxCost, dpUp[u][x][1] + dpDown[v][k - x][1] );
            maxCost = max( maxCost, dpUp[u][x][2] + dpDown[v][k - x][1] );
            maxCost = max( maxCost, dpUp[u][x][1] + dpDown[v][k - x][2] );
            maxCost = max( maxCost, dpUp[u][x][2] + dpDown[v][k - x][2] );

            maxCost = max( maxCost, dpUp[v][x][0] + dpDown[u][k - x][0] - a[v] );
            maxCost = max( maxCost, dpUp[v][x][0] + dpDown[u][k - x][1] );
            maxCost = max( maxCost, dpUp[v][x][0] + dpDown[u][k - x][2] );
            maxCost = max( maxCost, dpUp[v][x][1] + dpDown[u][k - x][0] - a[v] );
            maxCost = max( maxCost, dpUp[v][x][2] + dpDown[u][k - x][0] - a[v] );
            maxCost = max( maxCost, dpUp[v][x][1] + dpDown[u][k - x][1] );
            maxCost = max( maxCost, dpUp[v][x][2] + dpDown[u][k - x][1] );
            maxCost = max( maxCost, dpUp[v][x][1] + dpDown[u][k - x][2] );
            maxCost = max( maxCost, dpUp[v][x][2] + dpDown[u][k - x][2] );
        }

        for ( int x = 1; x <= k; x++ ) {
            dpUp[u][x][0] = max( dpUp[u][x][0], max( max( dpUp[v][x - 1][0] + b[u] - a[v], dpUp[v][x - 1][1] + b[u] - a[v] ), dpUp[v][x - 1][2] + b[u] - a[v] ) );
            dpUp[u][x][1] = max( dpUp[u][x][1], dpUp[v][x][0] );
            dpUp[u][x][2] = max( dpUp[u][x][2], max( dpUp[v][x][1], dpUp[v][x][2] ));

            dpDown[u][x][0] = max( dpDown[u][x][0], max( max( dpDown[v][x - 1][0] + b[u] - a[u], dpDown[v][x - 1][1] + b[u] ), dpDown[v][x - 1][2] + b[u] ) );
            dpDown[u][x][1] = max( dpDown[u][x][1], dpDown[v][x][0] - a[u] );
            dpDown[u][x][2] = max( dpDown[u][x][2], max( dpDown[v][x][1], dpDown[v][x][2] ));
        }
    }

    maxCost = max( maxCost, dpUp[u][k][0] );
    maxCost = max( maxCost, dpUp[u][k][1] );
    maxCost = max( maxCost, dpUp[u][k][2] );
    maxCost = max( maxCost, dpDown[u][k][0] );
    maxCost = max( maxCost, dpDown[u][k][1] );
    maxCost = max( maxCost, dpDown[u][k][2] );
}

int main() {
    int n;

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

    dfs( 1, 0 );

    cout << maxCost << "\n";

    return 0;
}

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