#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <cstdlib>
#include <cctype>
#include <ctime>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <utility>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <list>
#include <bitset>
#include <complex>
//using namespace __gnu_pbds;
using namespace std;
#define f first
#define s second
#define endl '\n'
#define PB pop_back
#define pb push_back
#define mp make_pair
//#define int long long
#define sz(s) (int)s.size()
#define seper(n) setprecision(n)
#define all(v) v.begin(),v.end()
#define mem(a,b) memset(a,b,sizeof a)
#define IOS ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
//template<typename T>using ordered_set = tree<T , null_type , less_equal<T> , rb_tree_tag , tree_order_statistics_node_update>;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef map<int , int> mii;
typedef pair<int , int> pii;
typedef map<string , int> msi;
const int MAXN = 5e2 + 10;
int n , m , u , v , cnt , a[MAXN] , dp[2 + 1][MAXN][MAXN << 2];
mii mpp;
vector<int> adj[MAXN];
void dfs(int u , int p)
{
int num = cnt;
if(u != p)
cnt += sz(adj[u]);
else
cnt += sz(adj[u]) + 1;
for(auto v : adj[u])
if(v != p)
dfs(v , u);
///base
for(int i = 1 ; i <= m ; i ++)
dp[0][i][num] = a[u] , dp[1][i][num] = a[u];
///update
for(auto v : adj[u])
if(v != p)
{
num ++;
for(int i = 0 ; i <= m ; i ++)
{
dp[0][i][num] = dp[0][i][num - 1] , dp[1][i][num] = dp[1][i][num - 1];
for(int j = 0 ; i - j - 1 >= 0 ; j ++)
{
dp[0][i][num] = max(dp[0][i][num] , dp[0][j][mpp[v]] + dp[1][i - j - 1][num - 1]);
if(i - j - 2 >= 0)
for(int bo = 0 ; bo < 2 ; bo ++)
{
if(!bo)
dp[bo][i][num] = max(dp[bo][i][num] , dp[bo ^ 1][j][mpp[v]] + dp[bo][i - j - 2][num - 1]);
else
dp[bo][i][num] = max(dp[bo][i][num] , dp[bo][j][mpp[v]] + dp[bo][i - j - 2][num - 1]);
}
}
}
}
mpp[u] = num;
}
int main()
{
IOS
scanf("%d%d" , &n , &m);
for(int i = 0 ; i < n ; i ++)
scanf("%d" , &a[i]);
for(int i = 0 ; i < n - 1 ; i ++)
scanf("%d%d" , &u , &v) , u -- , v -- , adj[u].pb(v) , adj[v].pb(u);
dfs(0 , 0);
printf("%d\n" , dp[0][m][mpp[0]]);
return 0;
}
Compilation message
dostavljac.cpp: In function 'int main()':
dostavljac.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d" , &n , &m);
~~~~~^~~~~~~~~~~~~~~~~~
dostavljac.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d" , &a[i]);
~~~~~^~~~~~~~~~~~~~
dostavljac.cpp:94:62: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d" , &u , &v) , u -- , v -- , adj[u].pb(v) , adj[v].pb(u);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
1144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
2032 KB |
Output is correct |
| 2 |
Correct |
21 ms |
1148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
1144 KB |
Output is correct |
| 2 |
Correct |
292 ms |
3832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
558 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
179 ms |
2728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
206 ms |
2936 KB |
Output is correct |
| 2 |
Correct |
1374 ms |
6744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1211 ms |
6392 KB |
Output is correct |
| 2 |
Correct |
465 ms |
3960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2080 ms |
8152 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
