#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;
template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
for (auto &i : a) {
is >> i;
}
return is;
}
vector<int> a;
vector<vector<int>> g;
vector<int> sz;
vector<vector<vector<ll>>> dp;
void dfs(int v, int p = -1) {
sz[v] = 1;
for (auto u : g[v]) {
if (u != p) {
dfs(u, v);
sz[v] += sz[u];
}
}
dp[v].resize(2, vector<ll>(3, infll));
dp[v][0][0] = 0;
dp[v][0][1] = a[v];
int cur = 1;
for (auto u : g[v]) {
if (u != p) {
vector<vector<ll>> dpp(cur + sz[u] + 1, vector<ll>(3, infll));
for (int i = 0; i <= cur; ++i) {
for (int j = 0; j <= sz[u]; ++j) {
dpp[i + j][0] = min(dpp[i + j][0], dp[v][i][0] + dp[u][j][0]);
dpp[i + j][0] = min(dpp[i + j][0], dp[v][i][0] + dp[u][j][1]);
dpp[i + j][0] = min(dpp[i + j][0], dp[v][i][0] + dp[u][j][2]);
dpp[i + j][1] = min(dpp[i + j][1], dp[v][i][1] + dp[u][j][0]);
dpp[i + j][2] = min(dpp[i + j][2], dp[v][i][2] + dp[u][j][0]);
if (i + j + 1 <= cur + sz[u]) {
dpp[i + j + 1][2] = min(dpp[i + j + 1][2], dp[v][i][2] + dp[u][j][1]);
}
dpp[i + j][2] = min(dpp[i + j][2], dp[v][i][2] + dp[u][j][2]);
if (i + j + 2 <= cur + sz[u]) {
dpp[i + j + 2][2] = min(dpp[i + j + 2][2], dp[v][i][1] + dp[u][j][1]);
}
if (i + j + 1 <= cur + sz[u]) {
dpp[i + j + 1][2] = min(dpp[i + j + 1][2], dp[v][i][1] + dp[u][j][2]);
}
}
}
dp[v] = dpp;
cur += sz[u];
}
}
}
int32_t main() {
#ifdef LOCAL
freopen("/tmp/input.txt", "r", stdin);
#else
ios::sync_with_stdio(false);
cin.tie(nullptr);
#endif
int n, m;
cin >> n >> m;
assert(m == n - 1);
a.resize(n);
cin >> a;
g.resize(n);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
g[u].push_back(v);
g[v].push_back(u);
}
sz.resize(n);
dp.resize(n);
dfs(0);
int q;
cin >> q;
while (q--) {
int s;
cin >> s;
int l = 0, r = n + 1;
while (r - l > 1) {
int mid = (l + r) / 2;
if (min({dp[0][mid][0], dp[0][mid][1], dp[0][mid][2]}) <= s) {
l = mid;
} else {
r = mid;
}
}
cout << l << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
15696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
15696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
1372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
15696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
