oj.uz

Submission #934308

# Submission time Handle Problem Language Result Execution time Memory
934308 2024-02-27T06:59:07 Z UmairAhmadMirza Chase (CEOI17_chase) C++14
0 / 100
 4000 ms 91136 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;
}
int ans=0;
int org_v;
void reroot(int a,int b){
  for(int v=1;v<org_v;v++){
    dp[b][v]=0;
    int c1=0;
    int sm=0;
    for(auto i:adj[b]){
      if(i==a)
        continue;
      dp[b][v]=max(dp[b][v],dp[i][v]);
      c1=max(c1,pei[i]);
    }
    c1*=-1;
    for(auto i:adj[b]){
      if(i==a)
        continue;
      sm+=pei[i];
      c1=max(c1,dp[i][v-1]);
    }
    dp[b][v]=max(dp[b][v],sm+c1);
  }
  for(int v=1;v<org_v;v++){
    dp[a][v]=0;
    int c1=0;
    int sm=0;
    for(auto i:adj[a]){
      dp[a][v]=max(dp[a][v],dp[i][v]);
      c1=max(c1,pei[i]);
    }
    c1*=-1;
    for(auto i:adj[a]){
      sm+=pei[i];
      c1=max(c1,dp[i][v-1]);
    }
    dp[a][v]=max(dp[a][v],sm+c1);
  }
}
void reroot_dfs(int node,int par){
  ans=max(ans,dp[node][org_v]);
  for(auto i:adj[node]){
    if(i==par)
      continue;
    reroot(i,node);
    reroot_dfs(i,node);
    reroot(node,i);
  }
}
signed main(){
  int n,v;
  cin>>n>>v;
  org_v=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);
  }
  dfs(1);
  reroot_dfs(1,-1);
  cout<<ans<<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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 91136 KB Output is correct
2 Correct 526 ms 91012 KB Output is correct
3 Execution timed out 4026 ms 88168 KB Time limit exceeded
4 Halted 0 ms 0 KB -

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 -