Submission #349521

#	Time	Username	Problem	Language	Result	Execution time	Memory
349521		doowey	Chase (CEOI17_chase)	C++14	0 / 100	1784 ms	253292 KiB

chase

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 1;
const int D = 101;
const ll inf = (ll)1e18;

vector<int> T[N];
ll sol;
ll p[N];
ll dp[N][D];
ll dp2[N][D][2];

int v;

void upd(ll &a, ll b){
    a=max(a,b);
}

void dfs(int u, int pp){
    for(auto x : T[u]){
        if(x==pp) continue;
        dfs(x,u);
    }
    ll sum = 0;
    for(auto x : T[u]){
        sum += p[x];
    }
    dp[u][1]=sum;
    dp2[u][1][1]=sum;
    for(auto x : T[u]){
        if(x==pp)continue;

        for(int a = 1; a <= v; a ++ ){
            for(int b = 1;  a + b <= v; b ++ ){
                for(int q = 0; q < 2; q ++ ){
                    sol = max(sol, dp[u][a]+dp2[x][b][q]-(q*p[u]));
                    sol = max(sol, dp2[u][a][q]+dp[x][b]-(q*p[x]));
                }
            }
        }

        // update dp
        for(int i = 1; i <= v; i ++ ){
            dp[u][i]=max(dp[u][i],dp[x][i]);
            if(i + 1 <= v){
                dp[u][i+1]=max(dp[u][i+1],dp[x][i]+sum-p[x]);
            }
        }
        for(int b = 0; b < 2; b ++ ){
            for(int i = 1; i <= v; i ++ ){
                dp2[u][i][0]=max(dp2[u][i][0],dp2[x][i][b]-(b*p[u]));
                if(i + 1 <= v){
                    dp2[u][i+1][1]=max(dp2[u][i+1][1],dp2[x][i][b]-(b*p[u]));
                }
            }
        }
    }
    for(int a = 0 ; a <= v; a ++ ){
        sol = max(sol,dp[u][a]);
        for(int b = 0 ; b < 2; b ++ ){
            sol = max(sol,dp2[u][a][b]);
        }
    }
}

int main(){
    fastIO;
    //freopen("in.txt","r",stdin);
    int n;
    cin >> n >> v;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= v; j ++ ){
            dp[i][j]=-inf;
            for(int d = 0; d < 2; d ++ ){
                dp2[i][j][d]=-inf;
            }
        }
    }
    for(int i = 1; i <= n; i ++ ){
        cin >> p[i];
    }
    int u, v;
    for(int i = 1; i < n; i ++ ){
        cin >> u >> v;
        T[u].push_back(v);
        T[v].push_back(u);
    }
    dfs(1,-1);
    cout << sol << "\n";
    return 0;
}

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