#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define inf 1e15
#define N 1000
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tuple<int,int,int> tiii;
typedef pair<int,int> pii;
int n,m,q,cost[N+5],sz[N+5],vis[N+5],dp[N+5][N+5][3];
vector<int> g[N+5];
void init(int x,int ata){
vis[x]=1;
for(auto u:g[x])
if(u!=ata) init(u,x);
}
void dfs(int x,int ata){
sz[x]=1;
dp[x][0][0]=0;
dp[x][1][2]=cost[x];
for(auto u:g[x]){
if(u==ata) continue;
dfs(u,x);
for(int i=sz[x];i>=0;i--){
for(int j=1;j<=sz[u];j++){
dp[x][i+j][0]=min(dp[x][i+j][0],dp[x][i][0]+dp[u][j][0]);
dp[x][i+j][0]=min(dp[x][i+j][0],dp[x][i][0]+dp[u][j][1]);
dp[x][i+j][1]=min(dp[x][i+j][1],dp[x][i][1]+dp[u][j][0]);
dp[x][i+j][1]=min(dp[x][i+j][1],dp[x][i][1]+dp[u][j][1]);
dp[x][i+j][1]=min(dp[x][i+j][1],dp[x][i][1]+dp[u][j][2]);
dp[x][i+j][1]=min(dp[x][i+j][1],dp[x][i][0]+dp[u][j][1]);
dp[x][i+j][1]=min(dp[x][i+j][1],dp[x][i][0]+dp[u][j][2]);
dp[x][i+j][2]=min(dp[x][i+j][2],dp[x][i][2]+dp[u][j][0]);
}
}
sz[x]+=sz[u];
}
for(int i=sz[x];i>0;i--)
dp[x][i][1]=min(dp[x][i][1],dp[x][i-1][1]+cost[x]);
}
void solve(){
cin >> n >> m;
for(int i=1;i<=n;i++)
cin >> cost[i];
for(int i=0;i<m;i++){
int x,y;
cin >> x >> y;
g[x].pb(y);
g[y].pb(x);
}
for(int i=0;i<n+5;i++)
for(int j=0;j<n+5;j++)
dp[i][j][0]=dp[i][j][1]=dp[i][j][2]=inf;
for(int i=1;i<=n;i++){
if(!vis[i]){
g[0].pb(i);
init(i,0);
}
}
dfs(0,0);
vector<pii> ans;
for(int i=0;i<=n;i++){
pii p={dp[0][i][0],i};
while(!ans.empty() && ans.back().fr>=p.fr)
ans.pop_back();
ans.pb(p);
}
cin >> q;
while(q--){
int x;
cin >> x;
pii p={x,n};
int t=upper_bound(all(ans),p)-ans.begin()-1;
cout << ans[t].sc << "\n";
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int test=1;
//~ cin >> test;
while(test--) solve();
}
# | 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... |