Submission #245828

#TimeUsernameProblemLanguageResultExecution timeMemory
245828kshitij_sodaniChase (CEOI17_chase)C++17
40 / 100
2882 ms524292 KiB
/* https://www.oi.edu.pl/old/ioi/downloads/ioi2005-tasks-and-solutions-a5.pdf */ #include <bits/stdc++.h> using namespace std; typedef int64_t llo; #define mp make_pair #define pb push_back #define a first #define b second //#define endl '\n' llo n,m; llo it[100001]; llo co[100001]; vector<llo> adj[100001]; llo dp[100001][101][2]; llo dp2[100001][101][2]; llo ans=0; vector<pair<llo,int>> ac[101][2]; void dfs(llo no,llo par2=-1){ for(llo i=1;i<=m;i++){ dp[no][i][0]=0; dp2[no][i][0]=0; dp[no][i][1]=co[no]; dp2[no][i][1]=co[no]; } for(auto j:adj[no]){ if(j==par2){ continue; } dfs(j,no); } for(int i=0;i<=m;i++){ ac[i][0].clear(); ac[i][1].clear(); } for(auto j:adj[no]){ if(j==par2){ continue; } for(llo i=0;i<=m;i++){ llo x=0; llo y=0; if(i>0){ x=max(x,dp[j][i-1][0]+co[no]); if(i>1){ x=max(x,dp[j][i-1][1]+co[no]-it[no]); } } dp[no][i][1]=max(dp[no][i][1],x); y=max(y,dp[j][i][0]); if(i>0){ y=max(y,dp[j][i][1]-it[no]); } dp[no][i][0]=max(dp[no][i][0],y); ac[i][0].pb({max(x,y),j}); x=0; y=0; if(i>0){ x=max(x,dp2[j][i-1][0]+co[no]-it[j]); if(i>1){ x=max(x,dp2[j][i-1][1]+co[no]-it[j]); } y=max(y,dp2[j][i][1]); } y=max(y,dp2[j][i][0]); dp2[no][i][0]=max(dp2[no][i][0],y); dp2[no][i][1]=max(dp2[no][i][1],x); ac[i][1].pb({max(x,y),j}); } } ans=max(ans,dp[no][m][0]); ans=max(ans,dp[no][m][1]); ans=max(ans,dp2[no][m][0]); ans=max(ans,dp2[no][m][1]); /*for(llo i=0;i<=m;i++){ if(ac[i][0].size()>0 and ac[m-i][1].size()>0){ if(ac[i][0][0].b==ac[m-i][1][0].b){ if(ac[i][0].size()>1){ ans=max(ans,ac[i][0][1].a+ac[m-i][1][0].a); } if(ac[m-i][1].size()>1){ ans=max(ans,ac[i][0][0].a+ac[m-i][1][1].a); } } else{ ans=max(ans,ac[i][0][0].a+ac[m-i][1][0].a); } } } */ } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n>>m; for(llo i=0;i<n;i++){ cin>>it[i]; } for(llo i=0;i<n-1;i++){ llo aa,bb; cin>>aa>>bb; aa--; bb--; adj[aa].pb(bb); adj[bb].pb(aa); co[aa]+=it[bb]; co[bb]+=it[aa]; } if(n<=1000){ for(int i=0;i<n;i++){ dfs(i); } } dfs(0); cout<<ans<<endl; // cout<<max(dp[0][m][1],dp[0][m][0])<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...