首先需要发现一个结论:
最终答案的 MST 方案, 与原图的任意的一种 MST 方案相比, 最多只能有一条边的差别。
因为若有两条有差别的话, 那么一条染白, 一条染黑, 一定合法且更优。
设 sum 表示原图的一个 MST 答案, 讨论三种情况:
sum >X : 无解
sum=X : 枚举不在 MST 中的每条边, 求出强制其在 MST 中的答案。
设有 prob 条边的答案 =X。
先确定原图 MST 方案中那些边的颜色
p
p, 然后从
p
r
o
b
prob 条边中至少选一条与
p
p 颜色不同, 剩下的随便选。
答案为
2
m
−
2
∗
2
m
−
(
n
−
1
)
−
p
r
o
b
2
m
−2∗2
m−(n−1)−prob
所有边颜色方案-MST的边为同一颜色的方案
sum
<
X
sum<X :
与上一种情况类似, 设有
p
r
o
b
prob 条边满足答案
X
=X, 有
b
a
n
ban 条边满足答案
<
X
<X
先确定原图 MST 方案那些边的颜色
p
p, 然后从
p
r
o
b
prob 条边中至少选一条与
p
p 颜 色不同，且剩下的边中有 ban 条边也要与
p
p 颜色相同(这样才能保证选出的边符合：选出的最小合法边集合=X)。
答案为
2
∗
(
2
m
−
(
n
−
1
)
−
b
a
n
−
2
m
−
(
n
−
1
)
−
b
a
n
−
p
r
o
b
)
2∗(2
m−(n−1)−ban
−2
m−(n−1)−ban−prob
)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,M=2e5+5;
const int mod=1e9+7;
struct node{int u,v,w;
}e[M*2];
struct point{int to,cs;
};
int t,n,m,x,sum=0,ans=0,tot=0;
int fa[N];
int mx[N][20],f[N][20];
int dep[N];
bool vis[M];
int pw[M];
vector<point> G[N];
bool cmp(const node &a,const node &b){return a.w<b.w;
}
int find(int x){if(fa[x]!=x) fa[x]=find(fa[x]);return fa[x];
}
void kruskal(){for(int i=1;i<=n;++i) fa[i]=i;sort(e+1,e+m+1,cmp);int t=0;for(int i=1;i<=m;++i){int uf=find(e[i].u);int vf=find(e[i].v);if(uf!=vf){fa[uf]=vf;t++;sum+=e[i].w;vis[i]=1;G[e[i].u].push_back({e[i].v,e[i].w});G[e[i].v].push_back({e[i].u,e[i].w});if(t==n-1) break;}}
}
void dfs(int u,int fa){f[u][0]=fa;for(int i=1;i<=18;++i){f[u][i]=f[f[u][i-1]][i-1];mx[u][i]=max(mx[u][i-1],mx[f[u][i-1]][i-1]);}for(int i=0;i<G[u].size();++i){int v1=G[u][i].to,w1=G[u][i].cs;if(v1==fa) continue;mx[v1][0]=w1;dep[v1]=dep[u]+1;dfs(v1,u);}
}
int lca(int x,int y){int res=0;if(dep[x]<dep[y]) swap(x,y);for(int i=18;i>=0;--i)if(dep[f[x][i]]>=dep[y]){res=max(res,mx[x][i]);x=f[x][i];}if(x==y) return res;for(int i=18;i>=0;--i)if(f[x][i]!=f[y][i]){res=max(res,max(mx[x][i],mx[y][i]));x=f[x][i];y=f[y][i];}return max(res,max(mx[x][0],mx[y][0]));
}
signed main(){freopen("zhuzhu.in","r",stdin);freopen("zhuzhu.out","w",stdout);cin>>t;pw[0]=1;for(int i=1;i<=2e5;++i)pw[i]=pw[i-1]*2%mod;while(t--){scanf("%lld%lld%lld",&n,&m,&x);for(int i=1;i<=m;++i) scanf("%lld%lld%lld",&e[i].u,&e[i].v,&e[i].w);sum=0;ans=0;tot=0;memset(vis,0,sizeof(vis));memset(dep,0,sizeof(dep));for(int i=1;i<=n;++i) G[i].clear();kruskal();if(sum>x){printf("0\n");continue;}if(sum==x){dep[1]=1;dfs(1,0);for(int i=1;i<=m;++i){if(vis[i]) continue;int val=lca(e[i].u,e[i].v);if(e[i].w==val) tot++;}ans=((pw[n-1+tot]-2)%mod)*pw[m-(n-1)-tot]%mod;}else{dep[1]=1;dfs(1,0);int cnt=0;for(int i=1;i<=m;++i){if(vis[i]) continue;int val=lca(e[i].u,e[i].v);if(sum-val+e[i].w<x) tot++;else if(sum-val+e[i].w==x) cnt++;}ans=2*(pw[m-(n-1)-tot]-pw[m-(n-1)-tot-cnt]+mod)%mod;}printf("%lld\n",ans);}fclose(stdin);fclose(stdout);return 0;
}