#include <bits/stdc++.h>
using namespace std;
#define int long long
vector <vector <int> > g;
vector <int> a;
vector <int> h;
vector <vector <int> > pred;
vector <int> tin, tout;
bool pr(int a, int b)
{
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int len(int a, int b)
{
if(pr(a, b))
{
return h[b] - h[a];
}
else if(pr(b, a))
{
return h[a] - h[b];
}
else
{
int sum = h[a] + h[b];
for(int j = pred.size() - 1; j >= 0; j--)
{
if(!pr(pred[j][a], b))
{
a = pred[j][a];
}
}
a = pred[0][a];
return sum - 2 * h[a];
}
}
int timer = 0;
vector <int> eiler;
void dfs(int v, int p = -1)
{
tin[v] = timer++;
eiler.push_back(v);
for(int i = 0; i< g[v].size(); i++)
{
int to = g[v][i];
if(to != p)
{
h[to] = h[v] + 1;
pred[0][to] = v;
dfs(to, v);
}
}
tout[v] = timer++;
}
signed main(){
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// cout.tie(NULL);
int n, m;
cin >> n >> m;
a.resize(n);
g.resize(n);
h.resize(n);
tin.resize(n);
tout.resize(n);
int t = log2(n) + 1;
pred.resize(t, vector <int> (n));
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
for(int i = 0; i < n - 1; i++)
{
int a, b;
cin >> a >> b;
a--;
b--;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(0);
for(int i = 1; i < t; i++){
for(int j = 0; j < n; j++)
{
pred[i][j] = pred[i - 1][pred[i - 1][j]];
}
}
vector <vector <int> > dist(n, vector <int> (n));
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++)
{
dist[i][j] = len(i, j);
}
}
vector <vector <int> > dp(n, vector <int> (m + 1, -1e10));
dp[0][0] = 0;
dp[0][1] = a[0];
int ans = 0;
ans = a[0];
for(int i = 1; i < n; i++)
{
for(int j = 0; j < i; j++)
{
int d = dist[eiler[i]][eiler[j]];
for(int t = 0; t + d <= m; t++)
{
if(t + d + 1 <= m)
{
dp[i][t + d + 1] = max(dp[i][t + d + 1], dp[j][t] + a[eiler[i]]);
}
dp[i][t + d] = max(dp[i][t + d], dp[j][t]);
}
d = d + h[eiler[i]] - h[eiler[j]];
for(int t = 0; t + d <= m; t++)
{
if(t + d >= 0)
{
dp[i][t + d] = max(dp[i][t + d], dp[j][t]);
}
if(t + d + 1 <= m && t + d+ 1 >= 0)
{
dp[i][t + d + 1] = max(dp[i][t + d + 1], dp[j][t] + a[eiler[i]]);
}
}
}
for(int t = 0; t <= m; t++)
{
ans = max(ans, dp[i][t]);
}
}
cout << ans;
return 0;
}
Compilation message
dostavljac.cpp: In function 'void dfs(long long int, long long int)':
dostavljac.cpp:44:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i< g[v].size(); i++)
~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
82 ms |
1280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
88 ms |
1536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
306 ms |
2944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
596 ms |
4472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
