제출 #934310

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
934310		UmairAhmadMirza	Chase (CEOI17_chase)	C++17	40 / 100	4067 ms	91224 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;
}
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: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30