读题发现给出的图肯定是森林。因为"这 $M$ 组朋友不可能将 $A$ 分享给别人的答案重新分享给$A$"。

那么我们先考虑较为简单的情形，就是一棵树。对于森林，只需要建一个超级原点将各个树合并起来即可。

稍微转化一下就可以得到更形式化的要求的东西：在给定代价内，选出一些大小大于 $1$ 的连通块，使所有连通块的大小之和最大。

显然要考虑树形 dp，难点在于如何设状态以及转移。

第一反应是设 $f_{u,i}$ 表示在 $u$ 子树内花费 $i$ 时最多能选到的点数。但是这样先不说转移，单单是状态就已经巨大无比，不可能做的下去。

我们发现 $S_i$ 值域很大，但是点数非常的小。因此想到一个 dp 中相当常见的方法：交换下标与值的意义。dp 状态实际上就是两个东西对应关系，所以下标与值反过来也是对应的。

因此，设 $f_{u,i}$ 表示，在 $u$ 子树内答案为 $i$ 时，所需代价。这样起码状态是 $n^2$ 的，然后考虑转移。

发现这样设完之后，还必须知道根节点有没有选上（注：这里选上不代表会贡献到答案里，比如单单激活一个点，不会让答案改变，但他被激活了，是潜在可以利用的点）。

这样之后似乎就可以转移了，但是我们发现，由于一个非常烦人的条件会让问题很复杂，就是连通块大小必须大于 $1$。那我们刚才的状态在转移起来的时候就会发现，对于 $u\ 和\ v\in son_u$，即使知道有没有选上还是无法更新答案。

比如，$v$ 被选上了，同时他已经在一个大小大于 $1$ 的连通块中了，然后 $u$ 也被选上了，但是他有可能已经在一个合法连通块中了，也有可能不在。而这两种情况是截然不同的，前者不会改变答案，但后者会让答案 $+1$，因为 $u$ 作为一个点虽然被激活但是大小为 $$，并不算在答案内，转移后，他会并进 $v$ 的连通块里。

所以状态应该修改成最终这样：$f_{u,i,0/1,0/1}$ 代表在u子树内，答案为 $i$ 时，$u$ 是否激活，$u$ 是否在一个合法连通块中，时所需的最小花费。

假设超级原点是 $n+1$ 的话，那最终答案就是最大的 $x$，使得 $f_{n+1,x,0,0}$ 小于等于给定钱数。

最后最麻烦的转移来了：

f[x][j+k+2][1][1]=min(f[x][j+k+2][1][1],f[x][j][1][0]+f[to][k][1][0]);
f[x][j+k+1][1][1]=min(f[x][j+k+1][1][1],f[x][j][1][0]+f[to][k][1][1]);
f[x][j+k+1][1][1]=min(f[x][j+k+1][1][1],f[x][j][1][1]+f[to][k][1][0]);
f[x][j+k][1][1]=min(f[x][j+k][1][1],f[x][j][1][1]+f[to][k][0][0]);
f[x][j+k][1][1]=min(f[x][j+k][1][1],f[x][j][1][1]+f[to][k][1][1]);
f[x][j+k][1][0]=min(f[x][j+k][1][0],f[x][j][1][0]+f[to][k][0][0]);
f[x][j+k][0][0]=min(f[x][j+k][0][0],f[x][j][0][0]+f[to][k][0][0]);
f[x][j+k][0][0]=min(f[x][j+k][0][0],f[x][j][0][0]+f[to][k][1][0]);
f[x][j+k][0][0]=min(f[x][j+k][0][0],f[x][j][0][0]+f[to][k][1][1]);

其实想要做到不重不漏的话，主要就是对于 $f_x\ 和\ f_{to}$ 后两维枚举所有情况。感觉转移比林克卡特树还麻烦。

按照树形背包的做法，倒序枚举已有大小 $j$ 和子树可能大小 $k$。树形背包虽然三层遍历，但是复杂度为 $n^2$，因为考虑两个点只会在 lca 处信息合并一次，那一个点的信息最多会与 $n$ 个点合并一次，因此是 $n^2$。

另外有一些初始化细节，可以直接在代码里看，不多赘述。

最后一步，再找答案时，我们不愿意要 $O(nQ)$ 这种擦边复杂度，$f_{x,i}$ 显然对于 $i$ 是有单调性的。所以直接二分即可。总复杂度可以做到 $O(n^2+Q\log_n)$。

欸，要是这样做你就错了。最后这一步看上去很显然，但是我被硬控很久。这玩意真有单调性吗？没有！为啥？

考虑还是那个恶心的条件：“连通块大小必须大于 $1$ ”。那么我们就不可能选出一个单点，就算他再小也不行，我们可能不得不花费一个更为高昂的代价找一个连通块周围的很贵的点，来凑出当前数量。这个代价可能甚至高昂到比我们再多选一个点，使得刚才的单点与这个点联通花费的代价还要高。

那不完了，没法二分了？其实还是可以。因为总体上这个是有单调的趋势的，只是相邻这样的可能会出现极端情况，所以每次二分发现 $mid$ 不行时，可以考虑 $mid+1$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e6+10;
ll n,m,Q;
ll v[N],rt[N],sz[N],num;
ll f[1010][1010][2][2];
bool vis[N];
struct edge{
    ll nxt,to;
}a[N];
ll head[N],tot;
void add(ll u,ll v) {
    a[++tot].nxt=head[u];
    a[tot].to=v;
    head[u]=tot;
}
void dfs0(ll x) {
	vis[x]=1;
	for(ll i=head[x];i;i=a[i].nxt) {
		ll to=a[i].to;
		if(vis[to]) continue;
		dfs0(to);
	}
}
void dfs(ll x) {
    vis[x]=1;
    sz[x]=1;
    for(ll i=1;i<=1005;i++) f[x][i][0][0]=f[x][i][1][0]=f[x][i][1][1]=1e12;
    f[x][0][1][0]=v[x];
    f[x][0][1][1]=1e12;
    for(ll i=head[x];i;i=a[i].nxt) {
        ll to=a[i].to;
        if(vis[to]) continue;
        dfs(to);
        for(ll j=sz[x];j>=0;j--) {
            for(ll k=sz[to];k>=0;k--) {
				f[x][j+k+2][1][1]=min(f[x][j+k+2][1][1],f[x][j][1][0]+f[to][k][1][0]);
				f[x][j+k+1][1][1]=min(f[x][j+k+1][1][1],f[x][j][1][0]+f[to][k][1][1]);
				f[x][j+k+1][1][1]=min(f[x][j+k+1][1][1],f[x][j][1][1]+f[to][k][1][0]);
				f[x][j+k][1][1]=min(f[x][j+k][1][1],f[x][j][1][1]+f[to][k][0][0]);
                f[x][j+k][1][1]=min(f[x][j+k][1][1],f[x][j][1][1]+f[to][k][1][1]);
                f[x][j+k][1][0]=min(f[x][j+k][1][0],f[x][j][1][0]+f[to][k][0][0]);
                f[x][j+k][0][0]=min(f[x][j+k][0][0],f[x][j][0][0]+f[to][k][0][0]);
                f[x][j+k][0][0]=min(f[x][j+k][0][0],f[x][j][0][0]+f[to][k][1][0]);
                f[x][j+k][0][0]=min(f[x][j+k][0][0],f[x][j][0][0]+f[to][k][1][1]);
            }
        }
        sz[x]+=sz[to];
    }
}
ll read() {
    ll as=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') as=as*10+(ch^48),ch=getchar();
    return as;
}
int main() {
//	freopen("wahaha.in","r",stdin);
//	freopen("wahaha.out","w",stdout);
    n=read(),m=read();
    v[n+1]=1e12;
    for(ll i=1;i<=n;i++) v[i]=read();
    for(ll i=1;i<=m;i++) {
        ll u=read(),v=read();
        add(u,v),add(v,u);
    }
    for(ll i=1;i<=n;i++) {
        if(!vis[i]) {
            rt[++num]=i;
            dfs0(i);
            add(n+1,i);
        }
    }
    memset(vis,0,sizeof(vis));
    dfs(n+1);
    Q=read();
    while(Q--) {
        ll now=read();
        ll l=2,r=n;
        while(l<r) {
            ll mid=(l+r+1)>>1;
            if(f[n+1][mid][0][0]<=now) l=mid;
            else {
            	if(f[n+1][mid+1][0][0]<=now) l=mid+1;
            	else r=mid-1;
			}
        }
        if(f[n+1][l][0][0]>now) l=0;
        cout<<l<<'\n';
    }
    return 0;
}
/*
7 6
1 2 1 2 2 2
1 2
2 3
3 4
1 5
5 6
6 7
9
9
8
7
6
5
4
3
2
1
*/