#include<bits/stdc++.h>
#define pii pair <int , int>
#define fi first
#define se second
#define arr3 array <int , 3>
#define int long long
using namespace std;
const int maxn = 1e3 + 7;
const int INF = 1e18;
bool vis[maxn];
int n , m , dp[2][2][maxn][maxn], sz[maxn], d[maxn] , ans[maxn];
vector <int> g[maxn];
void dfs(int u , int p)
{
vis[u] = 1;
sz[u] = 1;
dp[1][0][u][1] = d[u];
dp[0][1][u][0] = 0;
for(int v: g[u])
{
if(v == p) continue;
dfs(v , u);
for(int a = sz[u]; a >= 0; a--)
{
for(int b = sz[v]; b >= 1; b--)
{
dp[0][1][u][a+b] = min(dp[0][1][u][a+b] , dp[0][1][u][a] + min(dp[0][1][v][b] , dp[1][1][v][b]));
dp[1][0][u][a+b] = min(dp[1][0][u][a+b] , dp[1][0][u][a] + dp[0][1][v][b]);
dp[1][1][u][a+b] = min(dp[1][1][u][a+b] , dp[1][1][u][a] + min({dp[0][1][v][b] , dp[1][0][v][b] , dp[1][1][v][b]}));
dp[1][1][u][a+b] = min(dp[1][1][u][a+b] , dp[1][0][u][a] + min(dp[1][0][v][b] , dp[1][1][v][b]));
}
}
sz[u] += sz[v];
}
}
void solve()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> d[i];
for(int i = 1; i <= m; i++)
{
int u , v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= n; j++)
{
for(int a = 0; a < 2; a++)
{
for(int b = 0; b < 2; b++) dp[a][b][i][j] = INF;
}
}
ans[i] = INF;
}
ans[0] = 0;
ans[1] = INF;
for(int u = 1; u <= n; u++)
{
if(vis[u]) continue;
dfs(u , u);
for(int i = n; i >= 2; i--)
{
for(int k = 1; k <= i; k++)
{
ans[i] = min(ans[i] , ans[i - k] + min(dp[0][1][u][k] , dp[1][1][u][k]));
}
}
}
int q; cin >> q;
while(q--)
{
int x; cin >> x;
int s = upper_bound(ans+2 , ans+n+1 , x) - ans - 1;
s -= (s == 1);
cout << s << '\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |