/* * @Author: MaxPhast * @File: test.cpp * @Date: 2026-02-09 17:05:43 */ #include <bits/stdc++.h> using namespace std; #define int long long #define ii pair <int , int> #define iii pair <int , ii> #define iiii pair <ii , ii> #define FOR(i , l , r) for(int i = (l) , _r = (r) ; i <= _r ; ++ i) #define FORD(i , r , l) for(int i = (r) , _l = (l) ; i >= _l ; -- i) #define ALL(vec) vec.begin() , vec.end() #define UNI(vec) sort(ALL(vec)) , vec.erase(unique(ALL(vec)) , vec.end()) #define pb push_back #define MASK(i) (1ll << i) #define BIT(mask , i) ((mask >> i) & 1ll) #define ON(mask , i) (mask | MASK(i)) #define OFF(mask , i) (mask & (~MASK(i))) #define TURN(mask , i) (mask ^ MASK(i)) #define BP(mask) __builtin_popcountll(mask) #define sqr(x) (1ll * (x) * (x)) #define fi first #define se second #define oo 1e18 #define time() cerr << " \n " << "Time elapsed : " << 1000.0 * clock() / CLOCKS_PER_SEC << "ms." #define IO(TASK) if(fopen(#TASK".INP" , "r")){freopen(#TASK".INP" , "r" , stdin); freopen(#TASK".OUT" , "w" , stdout);} template <class X , class Y> bool maxz(X &a , const Y b) { if(a < b) { a = b; return true; } return false; } template <class X , class Y> bool minz(X &a , const Y b) { if(a > b) { a = b; return true; } return false; } namespace MaxPhast { const int N = 1e3 + 5; int n , m , q; int a[N] , sz[N] , dp[N][N][3] , mini[N]; vector <int> g[N]; void loang(int u , int pre) { sz[u] = 1; for(int &v : g[u]) if(v != pre) loang(v , u); } void dfs(int u , int pre) { dp[u][1][1] = a[u]; dp[u][0][0] = 0; for(int &v : g[u]) if(v != pre) { dfs(v , u); FORD(su , sz[u] , 0) { FOR(sv , 0 , sz[v]) { FOR(ju , 0 , 2) { FOR(jv , 0 , 2) { int new_s = su + sv; int new_j = (ju == 0 ? 0ll : min(2ll , ju + jv)); if(ju == 0) { if(jv == 0 || jv == 2) minz(dp[u][new_s][new_j] , dp[u][su][ju] + dp[v][sv][jv]); } else { minz(dp[u][new_s][new_j] , dp[u][su][ju] + dp[v][sv][jv]); } } } } } sz[u] += sz[v]; } } void solve() { cin >> n >> m; FOR(i , 1 , n) cin >> a[i]; FOR(i , 1 , m) { int u , v; cin >> u >> v; g[u].pb(v); g[v].pb(u); } FOR(i , 1 , n) if(!sz[i]) { loang(i , 0); g[i].pb(0); g[0].pb(i); } FOR(u , 0 , n) FOR(s , 0 , n) FOR(j , 0 , 2) dp[u][s][j] = oo; dfs(0 , -1); FOR(i , 0 , n) mini[i] = dp[0][i][0]; FORD(i , n - 1 , 0) minz(mini[i] , mini[i + 1]); cin >> q; while(q--) { int s; cin >> s; int l = 0 , r = n , res = 0; while(l <= r) { int mid = l + r >> 1; if(mini[mid] <= s) { res = mid; l = mid + 1; } else r = mid - 1; } cout << res << "\n"; } } } signed main() { ios_base :: sync_with_stdio(false) ; cin.tie(nullptr) ; cout.tie(nullptr) ; IO(test); MaxPhast :: solve(); time(); } /* */

dzumbus.cpp: In function 'int main()':
dzumbus.cpp:29:54: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 | #define IO(TASK) if(fopen(#TASK".INP" , "r")){freopen(#TASK".INP" , "r" , stdin); freopen(#TASK".OUT" , "w" , stdout);}
      |                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:167:5: note: in expansion of macro 'IO'
  167 |     IO(test);
      |     ^~
dzumbus.cpp:29:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 | #define IO(TASK) if(fopen(#TASK".INP" , "r")){freopen(#TASK".INP" , "r" , stdin); freopen(#TASK".OUT" , "w" , stdout);}
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:167:5: note: in expansion of macro 'IO'
  167 |     IO(test);
      |     ^~