！蒟蒻的P3329最小割树模版经性感猫娘调教无果仍保龄，求条

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int T,n,m,q,s,t,z,ans,sum;
struct edge
{
	int to,next,dis;
}e[1000005];
int h[500005],cnt=1;
void add(int x,int y,int d)
{
	e[++cnt].to=y;
	e[cnt].dis=d;
	e[cnt].next=h[x];
	h[x]=cnt;
}
void Add(int x,int y,int d)
{
	add(x,y,d);
	add(y,x,0);
}
int dis[500005],now[500005];
bool bfs(int s,int t)
{
	queue<int>q;
	for(int i=1;i<=n;i++)dis[i]=inf;
	q.push(s),dis[s]=1,now[s]=h[s];
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=h[x];i;i=e[i].next)
			if(dis[e[i].to]==inf&&e[i].dis)
			{
				q.push(e[i].to);
				now[e[i].to]=h[e[i].to];
				dis[e[i].to]=dis[x]+1;
				if(e[i].to==t)return 1;
			}
	}
	return 0;
}
int dfs(int t,int x,int f)
{
	if(x==t)return f;
	int k,res=0;
	for(int i=now[x];i&&f;i=e[i].next)
	{
		now[x]=i;
		if(e[i].dis&&dis[e[i].to]==dis[x]+1)
		{
			k=dfs(t,e[i].to,min(f,e[i].dis));
			if(k==0)dis[e[i].to]=inf;
			e[i].dis-=k,e[i^1].dis+=k;
			res+=k,f-=k;
		}
	}
	return res;
}
int x,y,d,v[1000005];
int dinic(int s,int t)
{
	ans=0;
	for(int i=2;i<=cnt;i++)
		e[i].dis=v[i];
	while(bfs(s,t))
		ans+=dfs(t,s,inf);
	return ans;
}
int f[500005];
int dist[505][505];
int t1[500005],t2[500005];
void build(int l,int r)
{
	if(l>=r)return;
	s=f[l],t=f[l+1];
	dist[s][t]=dist[t][s]=dinic(s,t);
	int cnt1=0,cnt2=0;
	for(int i=l;i<=r;i++)
		(dis[f[i]]^inf?t1[++cnt1]=f[i]:t2[++cnt2]=f[i]);
	for(int i=1;i<=cnt1;i++)f[i+l-1]=t1[i];
	for(int i=1;i<=cnt2;i++)f[l+cnt1+i-1]=t2[i];
	build(l,l+cnt1-1),build(l+cnt1,r);
	for(int i=l;i<l+cnt1;i++)for(int j=l+cnt1;j<=r;j++)
		dist[f[i]][f[j]]=dist[f[j]][f[i]]=min(min(dist[s][t],dist[f[i]][f[j]]),min(dist[f[i]][s],dist[t][f[j]]));
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--)
	{
		memset(dist,0x3f,sizeof(dist));
		cin>>n>>m,cnt=1;
		for(int i=1;i<=n;i++)
			h[i]=now[i]=0,f[i]=i;
		for(int i=1;i<=m;i++)
		{
			cin>>x>>y>>d;
			Add(x,y,d);
			Add(y,x,d);
		}
		for(int i=2;i<=cnt;i++)v[i]=e[i].dis;
		build(1,n);
		cin>>q;
		while(q--)
		{
			cin>>z,sum=0;
			for(int i=1;i<=n;i++)
				for(int j=i+1;j<=n;j++)
					if(dist[i][j]<=z)sum++;
			cout<<sum<<endl;
		}
		cout<<endl;
	}
	return 0;
}