十个点全T掉了...

#include<bits/stdc++.h>
using namespace std;


const int maxn = 605, maxm = 9005, INF = 0x3f3f3f3f;
struct GHT{//最小割树
	int a[maxn], cur[maxn], h[maxn], cnt;
    int node[maxn]; //存结点编号
    int vis[maxn]; //标记属于哪个连通块
    int ans[maxn][maxn];
    int N;
	int e[maxm << 1], ne[maxm << 1];
    int w[maxm << 1];//备份容量
	int val[maxm << 1];
	void init(int num){
		memset(h, -1, sizeof(h));
        for(int i=1;i<=num;i++) node[i]=i,vis[i]=0;
		cnt = -1; N=num;
	}
	void Addedge(int a, int b, int c) {
		e[++cnt] = b;
		ne[cnt] = h[a];
		val[cnt] = c;
        w[cnt] = c;
		h[a] = cnt;

		e[++cnt] = a;
		ne[cnt] = h[b];
        w[cnt] = c;
		val[cnt] = c;  //无向边时可以直接把这里改为c
		h[b] = cnt;
	}
	bool bfs(int s,int t){
		queue<int> que;
		que.push(s);
        for(int i=1;i<=N;i++) a[i]=0;
		//memset(a, 0, sizeof(a));
		a[s] = 1;
		while(!que.empty()){
			int u = que.front(); que.pop();
			for(int i = h[u]; ~i; i = ne[i]) {
				if(val[i] > 0 && a[e[i]] == 0) {
					a[e[i]] = a[u] + 1;
					que.push(e[i]);
				}
			}
		}
        if(a[t]) return 1;
        return 0;
        //return a[t]?1:0; //可以判断是否到达
	}
	int dfs(int u, int dist, int t){
		if(u == t || !dist ) return dist;
        int flow = 0;
		for(int &i = cur[u]; ~i; i = ne[i]) {
			if(a[e[i]] == a[u] + 1 && val[i] > 0){
				int tmp = dfs(e[i], min(dist-flow, val[i]), t);
				if(tmp > 0) {
                    flow+=tmp;
					val[i]-=tmp;
					val[i^1]+=tmp;
                    if(flow==dist) break;
				}
			}
		}
		return flow;// 增广容量
	}
	int dinic(int s,int t) {
		int res =0;
		while(bfs(s,t)){  
			for(int i = 0; i <= N; i ++) cur[i] = h[i];
			res += dfs(s,INF,t) ;
		}
		return res;
	}
    int cut(int x){
        vis[x]=1;
        for(int i=h[x];~i;i=ne[i]){
            if(val[i]&&!vis[e[i]]) cut(e[i]);
        }
    }
    void solve(int l,int r){ //分治   要先预处理 node[i]=i
        if(l==r) return ;
        for(int i=0;i<=cnt;i++) val[i]=w[i];
        int t[2][210]={0};
        memset(vis,0,sizeof(vis));
        int tmp=dinic(node[l],node[r]);
        cut(node[l]); //从左端出发
        for(int i=1;i<=N;i++){ //暴力更新答案
            if(vis[i]){
                for(int j=1;j<=N;j++){
                    if(!vis[j]){
                        ans[i][j]=ans[j][i]=min(ans[i][j],tmp);
                    }
                }
            }
        }
        for(int i=l;i<=r;i++) {
            t[vis[node[i]]][++t[vis[node[i]]][0]]=node[i];
        }
        for(int i=l,j=1;j<=t[0][0];j++,i++) node[i]=t[0][j];
        for(int i=l+t[0][0],j=1;j<=t[1][0];j++,i++) node[i]=t[1][j];
        solve(l,l+t[0][0]-1);solve(l+t[0][0],r);
    }

}GHT;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        GHT.init(n);
        while(m--){
            int u,v,c;
            scanf("%d%d%d",&u,&v,&c);
            GHT.Addedge(u,v,c);
        }
        GHT.solve(1,n);
        int q;
        scanf("%d",&q);
        while(q--){
            int x;
            scanf("%x",&x);
            int res=0;
            for(int i=1;i<=n;i++){
                for(int j=i+1;j<=n;j++){
                    if(GHT.ans[i][j]<=x) res++;
                }
            }
            printf("%d\n",res);
        }
        puts("");
    }
}