Submission #210081

#	Time	Username	Problem	Language	Result	Execution time	Memory
210081		arjun_9426	Chase (CEOI17_chase)	C++17	0 / 100	162 ms	96248 KiB

chase

// code written by Arjun Tomar
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int> 
#define pll pair<ll,ll>
#define mp(x,y) make_pair(x,y)
const ll inf=1e18;
const int nax=1e5+5;
const int gax=101;
vector<vector<int>> v(nax);
int vis[nax]={0};
map<int,vector<ll>> m[nax];

ll a[nax];
vector<vector<ll>> dp(nax,vector<ll>(gax,0));

void dfs(int ci){
    vis[ci]=1;
    ll g=a[ci];
    for(auto x : v[ci]){
        if(vis[x]==0) g+=a[x];
    }
    for(int i=1;i<gax;i++) dp[ci][i]=g;
    for(auto x : v[ci]){
        if(vis[x]==1) continue;
        dfs(x);
        for(int i=1;i<gax-1;i++){
            dp[ci][i+1]=max(dp[ci][i+1],dp[x][i]+dp[ci][1]-a[x]);
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n,r;
    cin>>n>>r;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n-1;i++){
        int x,y;cin>>x>>y;
        x--; y--;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(0);
    ll ans=-inf;
    for(int j=1;j<=r;j++){
        ans=max(dp[0][j]-a[0],ans);
    }
    cout<<ans<<'\n';
}

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