/*
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;
void dfs(llo no,llo par2=-1){
for(llo i=1;i<=m;i++){
dp[no][i][1]=co[no];
dp2[no][i][1]=co[no];
}
vector<pair<llo,llo>> ac[m+1][2];
for(auto j:adj[no]){
if(j==par2){
continue;
}
dfs(j,no);
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][i]+co[no]-it[j]);
}
}
dp[no][i][1]=max(dp[no][i][1],x);
y=max(y,dp[j][i][0]);
if(i>0){
y=max(y,dp[no][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,dp[j][i-1][0]+co[no]-it[no]);
if(i>1){
x=max(x,dp[j][i-1][1]+co[no]-it[no]);
}
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];
}
dfs(0);
cout<<ans<<endl;
return 0;
}
Compilation message
chase.cpp: In function 'void dfs(llo, llo)':
chase.cpp:36:26: warning: array subscript is above array bounds [-Warray-bounds]
x=max(x,dp[j][i-1][i]+co[no]-it[j]);
~~~~~~~~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
655 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
