oj.uz

Submission #934305

# Submission time Handle Problem Language Result Execution time Memory
934305 2024-02-27T06:45:07 Z UmairAhmadMirza Chase (CEOI17_chase) C++14
30 / 100
 267 ms 93124 KB 
#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);
  }
  // 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);
  //   cout<<dp[i][v]<<endl;
  // }
  dfs(1);
  cout<<dp[1][v]<<endl;
  return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 93124 KB Output is correct
2 Correct 171 ms 93008 KB Output is correct
3 Correct 267 ms 90160 KB Output is correct
4 Correct 186 ms 89808 KB Output is correct
5 Correct 226 ms 89936 KB Output is correct
6 Correct 181 ms 89912 KB Output is correct
7 Correct 182 ms 89936 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -