#include<bits/stdc++.h>
using namespace std;
#define int long long
#define db long double
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define BIT(x, pos) (((x)>>(pos)) & 1LL)
#define _(x) (1LL<<(x))
#define bitCnt(x) __builtin_popcountll(x)
#define turnOn(x, pos) ((x) = (_(pos)))
#define turnOff(x, pos) ((x) &= ~(_(pos)))
#define flipBit(x, pos) ((x) ^= (_(pos)))
#define lowBit(x) ((x) & (-x))
#define turnAll(x) (_(x)-1LL)
#define FOR(i, x, n) for(int i=x; i<n; i++)
#define F0R(i, n) FOR(i,0,n)
#define ROF(i, x, n) for(int i=n-1; i>=x; i--)
#define R0F(i, n) ROF(i,0,n)
const int INF = (int) 1E18;
const db inf = (db) 1E100;
const int MOD = (int) 1E9 + 7;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<pair<int, int>> vpii;
void File() {
#define file "test"
freopen(file".in", "r", stdin);
freopen(file".out", "w", stdout);
}
int expo(int a, int b, int mod) {
int res = 1;
while (b > 0) {
if (b & 1)res = (res * a) % mod;
a = (a * a) % mod;
b = b >> 1;
}
return res;
}
int mminvprime(int a, int b) { return expo(a, b - 2, b); }
int mod_add(int a, int b, int m) {
a = a % m;
b = b % m;
return (((a + b) % m) + m) % m;
}
int mod_mul(int a, int b, int m) {
a = a % m;
b = b % m;
return (((a * b) % m) + m) % m;
}
int mod_sub(int a, int b, int m) {
a = a % m;
b = b % m;
return (((a - b) % m) + m) % m;
}
int mod_div(int a, int b, int m) {
a = a % m;
b = b % m;
return (mod_mul(a, mminvprime(b, m), m) + m) % m;
}
/// ======================================================= - TEMPLATE - ======================================================= ///
int n, m;
vector <int> D;
vector <vector<int>> adj;
int G[1001][1001] = {0};
int F[1001][1001][3] = {0};
int bestG[1001][1001] = {0};
int bestF[1001][1001] = {0};
int Gall[1001] = {0};
void dfs(int u, int par)
{
//cerr << u << " -------------------" << endl;
F[u][0][1] = D[u];
G[u][0] = 0;
for (int v : adj[u])
{
if (v == par) continue;
dfs(v, u);
for (int i = 1; i <= n; i++)
{
if (F[v][i][0] >= INF) F[v][i][0] -= 1e10;
if (F[v][i][1] >= INF) F[v][i][1] -= 1e10;
if (G[v][i] >= INF) G[v][i] -= 1e10;
if (i >= 2) F[u][i][0] = min(F[u][i][0], min(F[v][i - 2][1] + D[u], F[v][i - 1][0] + D[u]));
F[u][i][1] = min(F[u][i][1], G[v][i] + D[u]);
G[u][i] = min(G[u][i], min(F[v][i][0], G[v][i]));
//cerr << u << " " << i << " " << G[u][i] << " " << F[u][i][0] << endl;
}
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//File();
cin >> n >> m;
D.assign(n + 1, 0);
adj.assign(n + 1, vector <int>());
for (int i = 1; i <= n; i++)
{
cin >> D[i];
}
for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
memset(F, 0x3f, sizeof(F));
memset(G, 0x3f, sizeof(G));
memset(bestG, 0x3f, sizeof(bestG));
memset(bestF, 0x3f, sizeof(bestF));
dfs(1, 0);
vector <pair<int, int>> cur;
cur.push_back({-INF, 0});
for (int i = 1; i <= n; i++)
{
cur.push_back({min(F[1][i][1], G[1][i]), i});
//cerr << i << " " << min(F[1][i][0], G[1][i]) << endl;
}
sort(all(cur));
vector <int> temp(n + 1, 0);
for (int i = 1; i <= n; i++)
{
cur[i].second = max(cur[i - 1].second, cur[i].second);
temp[i] = cur[i].first;
}
int q;
cin >> q;
while(q--)
{
int s;
cin >> s;
int pos = upper_bound(all(temp), s) - temp.begin();
pos--;
cout << cur[pos].second << endl;
}
return 0;
}
/*
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠿⢿⣿⣿⠿⠛⠿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠟⠉⠄⣀⡤⢤⣤⣈⠁⣠⡔⠶⣾⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⡿⠛⠋⠁⠄⠄⠄⣼⣿⠁⡀⢹⣿⣷⢹⡇⠄⠎⣿⣿⣿
⣿⣿⣿⠿⠛⠉⠁⠄⠄⠄⠄⠄⠄⠄⠹⣇⣀⣡⣾⣿⡿⠉⠛⠒⠒⠋⠉⢸
⡿⠋⠁⠄⠄⢀⣤⣤⡀⠄⠄⠄⠄⠄⠄⠈⠙⠛⠛⠉⠄⠄⠄⠄⠄⠄⠄⠈
⠄⠄⠄⠄⠄⢹⣧⡈⠿⣷⣄⣀⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⢀⣠⢄⣾
⠄⠄⠄⠄⠄⠈⠻⢿⣶⣌⣙⡛⠛⠿⠶⠶⠶⠶⠶⠖⣒⣒⣚⣋⡩⢱⣾⣿
⠄⠄⠄⠄⠄⠄⠄⠄⠈⠉⠛⠛⠛⠻⠿⠿⠟⠛⠛⠛⠉⢉⣥⣶⣾⣿⣿⣿
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠒⠶⣿⣿⣿⣿⣿⣿⣿⣿
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠈⠻⣿⣿⣿⣿⣿⣿
⣿⡿⠛⠛⠛⢻⣿⠿⠛⠛⠛⢿⣿⣿⡿⠛⠛⠛⢻⡟⠛⣿⡿⠛⣻⣿⣿⣿
⡟⠄⣼⣿⣿⣿⡇⠄⣾⣿⣧⠄⢻⡏⠄⣼⣿⣿⣿⡇⠄⡟⢀⣴⣿⣿⣿⣿
⡇⠄⣿⣿⣿⣿⡄⠄⣿⣿⣿⠄⢸⡇⠄⣿⣿⣿⣿⡇⠄⣀⠈⢻⣿⣿⣿⣿
⣿⣄⠈⠙⠛⢻⣧⡄⠙⠛⠉⣠⣿⣷⣄⠈⠙⠛⢹⡇⠄⣿⣧⠄⠻⣿⣿⣿
___ ___ _________ ________ ___ ___ ________ ________ ________ ________ ________ ________ ________
|\ \|\ \|\___ ___\ |\ __ \|\ \|\ \|\ __ \|\ ___ \|\ ____\ |\ __ \|\ ____\|\ __ \|\ __ \
\ \ \\\ \|___ \ \_| \ \ \|\ \ \ \\\ \ \ \|\ \ \ \\ \ \ \ \___| \ \ \|\ \ \ \___|\ \ \|\ /\ \ \|\ \
\ \ __ \ \ \ \ \ \ ____\ \ __ \ \ \\\ \ \ \\ \ \ \ \ ___ \ \ \\\ \ \ \ \ \ __ \ \ \\\ \
\ \ \ \ \ \ \ \ \ \ \___|\ \ \ \ \ \ \\\ \ \ \\ \ \ \ \|\ \ \ \ \\\ \ \ \____\ \ \|\ \ \ \\\ \
\ \__\ \__\ \ \__\ \ \__\ \ \__\ \__\ \_______\ \__\\ \__\ \_______\ \ \_______\ \_______\ \_______\ \_______\
\|__|\|__| \|__| \|__| \|__|\|__|\|_______|\|__| \|__|\|_______| \|_______|\|_______|\|_______|\|_______|
*/
Compilation message
dzumbus.cpp: In function 'void File()':
dzumbus.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | freopen(file".in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:34:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | freopen(file".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
47432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
47432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
268 ms |
49228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
47432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
