题意：
给出一个N个点M条边无向连通图，现在需要给每条边染色（黑/白），染色完毕后，算出一颗至少包含一条黑边与一条白边的最小生成树，要求这个生成树的权值和为X，求染色的方案数。
N≤1000,M≤2000N≤1000,M≤2000
分析：
Atcoder的题的确很锻炼思维。
首先，一个众所周知的最小生成树算法：破圈算法。这就是本题解法的基础。
简述一下破圈算法：
依次加入每一条边，若边连接的两点(u,v)不在一个联通块内，则连上这条边。
否则，如果连上这条边，就会形成一个环。我们加入这条边，再从环中删去一条权值最大的边，剩下的图一定没有环，并且各点的联通性不会改变。证明很容易，这里不再赘述。
再引到这道题上面来：
很容易发现，若原图的最小生成树中，同时含有黑、白两种颜色的边，则最后的权值一定是这颗最小生成树的权值。
那么再考虑原图的最小生成树中，所有边同为黑/白的情况。
这时候，我们肯定要加入一条颜色不同的边，并且还要使得最后的生成树权值尽量小。（注意，一定只会加入一条边，不会加入两条及以上，证明可以自己思考，很容易）
一个错误的想法：直接将所有未选入最小生成树的边，按照权值大小排序，如果选中第i条边，则要求前i-1条边的颜色与最小生成树的颜色一样，后面的边任意染色，第i条边与最小生成树反色。
这应该是最直观的想法，不过，如果对破圈算法的思想了解足够透彻，就会发现，这种思路绝对是错的。
根据破圈算法的描述，每次加入一条边时，删去的是整个环上权值最大的边。并且对于任意一种插入顺序，都能得到一个权值相同的最小生成树（可能有边不同）。重点就在这里：我们插入这条边后，同时还删去了一条原来的环上权值最大的边。所以每条边的贡献，应该是：该边的权值-最小生成树两点路径间最大权值。
所以，正确的方式应该是：按每条边的贡献由小到大排序，考虑所有：贡献+原最小生成树权值=X的边，分别计算其加入最小生成树的染色方案。
最后，还需要考虑如果X=最小生成树的权值和。
这种情况，还需要额外计算一种情况：即原最小生成树内同时含有黑、白边。
这种情况可以通过（总方案数-最小生成树所有边颜色相同的方案数）算出来。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 1010
#define MAXM 2010
#define MOD 1000000007
using namespace std;
int diff[MAXM];
struct node{int u,v,len;node () {}node (int u1,int v1,int len1):u(u1),v(v1),len(len1) {}bool operator < (const node &x) const {return len<x.len;}
}line[MAXM];
bool used[MAXM];
long long x,sum;
int fa[MAXN],fal[MAXN],deep[MAXN];
vector<int> a[MAXN],w[MAXN];
int get_fa(int x){if(fa[x]==0)return x;fa[x]=get_fa(fa[x]);return fa[x];
}
void build(int x,int fa1){fa[x]=fa1;deep[x]=deep[fa1]+1;for(int i=0;i<a[x].size();i++){if(a[x][i]==fa1){fal[x]=w[x][i];continue;}build(a[x][i],x);}
}
int find_max(int u,int v){int maxv=0;if(deep[u]<deep[v])swap(u,v);while(deep[u]>deep[v]){maxv=max(maxv,fal[u]);u=fa[u];}while(u!=v){maxv=max(maxv,max(fal[u],fal[v]));u=fa[u];v=fa[v];}return maxv;
}
int n,m,u,v,val;
long long bits[MAXM];
void prepare(){bits[0]=1;for(int i=1;i<=m;i++)bits[i]=(bits[i-1]*2ll)%MOD;
}
int main(){SF("%d%d",&n,&m);prepare();SF("%lld",&x);for(int i=0;i<m;i++){SF("%d%d%d",&u,&v,&val);line[i]=node(u,v,val);}sort(line,line+m);for(int i=0;i<m;i++){int u=get_fa(line[i].u);int v=get_fa(line[i].v);if(u!=v){fa[u]=v;sum+=line[i].len;a[line[i].u].push_back(line[i].v);a[line[i].v].push_back(line[i].u);w[line[i].u].push_back(line[i].len);w[line[i].v].push_back(line[i].len);used[i]=1;}}x=x-sum;if(x<0){PF("0");return 0;}memset(fa,0,sizeof fa);build(1,0);int cnt=0;for(int i=0;i<m;i++)if(used[i]==0){int maxd=find_max(line[i].u,line[i].v);diff[++cnt]=line[i].len-maxd;}sort(diff+1,diff+1+cnt);long long res=0;if(x==0)res=(bits[m]-2ll*bits[m-n+1]+2ll*MOD)%MOD;for(int i=1;i<=cnt;i++)if(x==diff[i]){res+=2ll*bits[cnt-i];res%=MOD;}PF("%lld",res);
}