Bichrome Spanning Tree
题意：
给出一个n个点，m条边的无向连通图，现在要给每条边染色，可以染成黑色或者白色。
现在要求在染色完毕后，找出一个至少包含一条黑边和一条白边的最小生成树，使其权值和为X。
问这样的染色方案有多少个？
题解：
题目要求找出一个至少包含一条黑边和白边的最小生成树，那么可能就会存在这种情况:原图的最小生成树所有边都为同色，那这不是我们要求的；我们这时就会去掉一条权值最大的边，再添一条边进来。
那么我们就可以算出包含指定边的最小生成树，方法就是先加我们指定的边，然后从小到大加边。
现在来解决这个问题，我们可以先求出原图的最小生成树，设其权值和为T，那么我们就对接下来的几种情况进行分析:
1.T>X 这种情况方案数为0；
2.T=X 这种情况下，因为边权可能会相等，所以可以继续进行删边加边的操作，直至第一种情况；
3.T<X 这种情况，我们就继续删边加边，找出使T=X相等的边的个数。
最后根据找到边的个数统计一下就好了：
对于第二种情况，设使T=X的边个数为a，其余边为b，那么答案就是(2^a-2)*2^b；
对于第三种情况，一开始使T<X的边只能同色，则方案数为2，则总答案为(2*2^a-2)*2^b，（a,b含义与上相同）。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = ,MOD = 1e9+;
int n,m;
ll X;
struct Edge{
int u,v,w;
bool operator < (const Edge& A)const{
return w<A.w;
}
}e[N];
int f[N];
int find(int x){
return f[x]==x ? x :f[x]=find(f[x]);
}
ll Kruskal(int edge){
ll sum = ;
for(int i=;i<=n+;i++) f[i]=i;
int fx,fy;
if(edge){
fx=find(e[edge].u),fy=find(e[edge].v);
f[fx]=fy;sum+=e[edge].w;
}
for(int i=;i<=m;i++){
if(i==edge) continue ;
fx=find(e[i].u);fy=find(e[i].v);
if(fx!=fy){
f[fx]=fy;
sum+=e[i].w;
}
}
return sum;
}
ll qp(ll a,ll b){
ll ans=;
while(b){
if(b&) ans=a*ans%MOD;
a=a*a%MOD;
b>>=;
}
return ans ;
}
int main(){
scanf("%d%d%lld",&n,&m,&X);
for(int i=;i<=m;i++)
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
sort(e+,e+m+);
ll t = Kruskal();
if(t>X){cout<<;return ;}
int cnt1=,cnt2=;
for(int i=;i<=m;i++){
ll now = Kruskal(i);
if(now==X) cnt1++;
else if(now>X) cnt2++;
}
if(t==X) cout<<(qp(,cnt1)-)*qp(,cnt2)%MOD;
else cout<<((ll)*qp(,cnt1)-)%MOD*qp(,cnt2)%MOD;
return ;
}