Submission #934306

#	Time	Username	Problem	Language	Result	Execution time	Memory
934306		UmairAhmadMirza	Chase (CEOI17_chase)	C++14	70 / 100	515 ms	90960 KiB

chase

#include <bits/stdc++.h>
using namespace std;
#define int long long
int const N=1e5+5;
int const V=103;
int dp[N][V];
int pei[N];
vector<int> adj[N];
void dfs(int node,int par=-1){
  for(auto i:adj[node]){
    if(i==par)
      continue;
    dfs(i,node);
  }
  for(int v=1;v<V;v++){
    int c1=0;
    int sm=0;
    for(auto i:adj[node]){
      if(i==par)
        continue;
      dp[node][v]=max(dp[node][v],dp[i][v]);
      c1=max(c1,pei[i]);
    }
    c1*=-1;
    for(auto i:adj[node]){
      if(i==par)
        continue;
      sm+=pei[i];
      c1=max(c1,dp[i][v-1]);
    }
    dp[node][v]=max(dp[node][v],sm+c1);
  }
  // cout<<node<<' '<<dp[node][0zzzzz]<<' '<<dp[node][1]<<' '<<dp[node][2]<<endl;
}
signed main(){
  int n,v;
  cin>>n>>v;
  for(int i=1;i<=n;i++)
    cin>>pei[i];
  for(int i=0;i<n-1;i++){
    int u,v;
    cin>>u>>v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  if(n<=1000){
    int ans=0;
    for(int i=1;i<=n;i++){
      for(int node=1;node<=n;node++)
        for(int vv=0;vv<V;vv++)
          dp[node][vv]=0;
      dfs(i);
      ans=max(ans,dp[i][v]);
    }
    cout<<ans<<endl;
  }
  else{
    dfs(1);
    cout<<dp[1][v]<<endl;
  }
  return 0;
}

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