#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
vector <int> v[DIMN];
int val[DIMN] , frm , fth[DIMN];
long long dp[2][DIMN][110] , dp2[2][DIMN][110],part[2][DIMN][110] , part2[2][DIMN][110];
long long sol;
void dfs (int nod , int tt){
int i , vecin , j;
long long sum;
sum = 0;
fth[nod] = tt;
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i];
if (vecin != tt){
sum += val[vecin];
}
}
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i];
if (vecin != tt){
dfs (vecin , nod);
//if (nod == 6)
// printf ("a");
for ( j = 0 ; j <= frm ; j++){
/// caz 1 : ai venit de jos in nod, te duci in jos spre vecin
sol = max(sol , dp[0][nod][j] + part2[0][vecin][frm - j]);
if (frm - j)
sol = max(sol , dp[0][nod][j] + part2[1][vecin][frm - j]);
if (j){
sol = max(sol , dp[1][nod][j] + part2[0][vecin][frm - j] + val[tt]);
sol = max(sol , dp[1][nod][j] + part2[1][vecin][frm - j] + val[tt]);
}
/// caz 2 : ai venit din jos spre vecin , te duci in nod apoi in jos
sol = max(sol , dp2[0][nod][j] + part[0][vecin][frm - j]);
if (frm - j)
sol = max(sol , dp2[0][nod][j] + part[1][vecin][frm - j] + val[nod]);
if (j){
sol = max(sol , dp2[1][nod][j] + part2[0][vecin][frm - j] + val[tt] - val[vecin]);
if (frm - j)
sol = max(sol , dp2[1][nod][j] + part2[1][vecin][frm - j] + val[tt] + val[nod] - val[vecin]);
}
}
//printf ("%d %lld\n",nod,sol);
/// adaugi vecin la setul de vecini cu care ai uni alti vecini
/// (ce coerenta fusei)
/// presupunem ca din vecin vrei sa te duci in nod
dp[1][nod][1] = max ( dp[1][nod][1] , sum );
for (j = 0 ; j <= frm ; j++){ /// vrei ca pana in nod sa fi consumat j
dp[0][nod][j] = max( dp[0][nod][j] , dp[0][vecin][j]);
/// nu ai aplicat nici in nod nici in vecin , ok
if (j)
dp[0][nod][j] = max( dp[0][nod][j] , dp[1][vecin][j] + val[nod]);
/// daca ai aplicat inainte in vecin, jerry nu mai vede in nod
if (j){ /// aplici in nod
/// daca nu am aplicat in vecin inainte
dp[1][nod][j] = max(dp[1][nod][j] , dp[0][vecin][j-1] + sum - val[vecin]);
/// daca am aplicat in vecin inainte
/// jerry nu o sa mai vada valoarea din nod, dra tom oricum o vede
if (j-1)
dp[1][nod][j] = max (dp[1][nod][j] , dp[1][vecin][j-1] + sum - val[vecin] + val[nod]);
}
sol = max(sol , max( dp[0][nod][j] , dp[1][nod][j] + val[tt]));
part[1][nod][j] = max(part[1][nod][j-1] , dp[1][nod][j]);
part[0][nod][j] = max(part[0][nod][j-1] , dp[0][nod][j]);
}
/// acum calculez dp2 , incep din i, ma duc in jos , consum j
dp2[1][nod][1] = max(dp2[1][nod][1] , sum);
for (j = 0 ; j <= frm ; j++){ /// vrei ca pana in nod sa fi consumat j
dp2[0][nod][j] = max( dp2[0][nod][j] , dp2[0][vecin][j]);
/// nu ai aplicat nici in nod nici in vecin , ok
if (j)
dp2[0][nod][j] = max( dp2[0][nod][j] , dp2[1][vecin][j]);
/// daca ai aplicat inainte in vecin, jerry nu mai vede in nod
if (j){ /// aplici in nod
/// daca nu am aplicat in vecin inainte
dp2[1][nod][j] = max(dp2[1][nod][j] , dp2[0][vecin][j-1] + sum);
/// daca am aplicat in vecin inainte
/// jerry nu o sa mai vada valoarea din nod, dra tom oricum o vede
if (j-1)
dp2[1][nod][j] = max (dp2[1][nod][j] , dp2[1][vecin][j-1] + sum);
}
sol = max(sol , max( dp2[0][nod][j] , dp2[1][nod][j] + val[tt]));
part2[1][nod][j] = max(part2[1][nod][j-1] , dp2[1][nod][j]);
part2[0][nod][j] = max(part2[0][nod][j-1] , dp2[0][nod][j]);
}
//printf ("%d %lld\n",nod,sol);
}
}
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n , i , x , y;
fscanf (fin,"%d%d",&n,&frm);
for (i=1;i<=n;i++)
fscanf (fin,"%d",&val[i]);
for (i=1;i<n;i++){
fscanf (fin,"%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
dfs (1 , 0);
fprintf (fout,"%lld" , sol);
return 0;
}
Compilation message
chase.cpp: In function 'void dfs(int, int)':
chase.cpp:13:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
chase.cpp:19:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
chase.cpp: In function 'int main()':
chase.cpp:122:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d",&n,&frm);
~~~~~~~^~~~~~~~~~~~~~~~~~~~
chase.cpp:124:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d",&val[i]);
~~~~~~~^~~~~~~~~~~~~~~~~~
chase.cpp:126:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d",&x,&y);
~~~~~~~^~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
2812 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
2812 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
766 ms |
362716 KB |
Output is correct |
| 2 |
Correct |
756 ms |
362340 KB |
Output is correct |
| 3 |
Correct |
455 ms |
10520 KB |
Output is correct |
| 4 |
Runtime error |
767 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
2812 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
