Submission #939611

#	Time	Username	Problem	Language	Result	Execution time	Memory
939611		vjudge1	Chase (CEOI17_chase)	C++17	70 / 100	235 ms	94036 KiB

chase

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1e5+5;
vector <int> g[N];
int fr_sum[N],x[N];
int dp[N][105];
int n,k;
void dfs(int v,int p){
    for(auto to : g[v]){
        if(to!=p){
            for(int i=1;i<=k;i++)dp[to][i]=max(dp[v][i],dp[v][i-1]+fr_sum[to]-x[v]);
            dfs(to,v);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>x[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
        fr_sum[v]+=x[u];
        fr_sum[u]+=x[v];
    }
    int ans=0;
    if(n<=1000){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                for(int t=0;t<=k;t++){
                    dp[j][t]=0;
                }
            }
            for(int j=1;j<=k;j++){
                dp[i][j]=fr_sum[i];
            }
            dfs(i,0);
            for(int j=1;j<=n;j++){
                for(int t=0;t<=k;t++){
                    ans=max(ans,dp[j][t]);
                }
            }
        }
        cout<<ans<<"\n";
        return 0;
    }
    for(int j=1;j<=k;j++){
        dp[1][j]=fr_sum[1];
    }
    dfs(1,0);
    for(int j=1;j<=n;j++){
        for(int t=0;t<=k;t++){
            ans=max(ans,dp[j][t]);
        }
    }
    cout<<ans<<"\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