Submission #9583291

---

Source Code Expand

#include<bits/stdc++.h>
const int maxn = 100100;
const int mod = 1e9 + 7;
typedef long long ll;
struct T{ int u, v, w; } e[maxn];
struct { int to,nxt,v; }way[maxn << 1];
inline ll pow(int a,int b,int ans = 1) {
	for(;b;b >>= 1,a = (ll) a * a % mod) if(b & 1)
		ans = (ll) ans * a % mod;
	return ans;
}
int h[maxn], num;
inline void link(int x,int y,int v) {
	way[++num] = {y,h[x],v}, h[x] = num;
	way[++num] = {x,h[y],v}, h[y] = num;
}
int bz[20][maxn], max[20][maxn], dep[maxn];
inline void dfs(int x,int f = 0) {
	dep[x] = dep[f] + 1;
	for(int i = 1;i < 20;++i) {
		bz[i][x] = bz[i - 1][bz[i - 1][x]];
		max[i][x] = std::max(max[i - 1][x], max[i - 1][bz[i - 1][x]]);
	}
	for(int i = h[x];i;i=way[i].nxt) if(way[i].to != f) {
		max[0][way[i].to] = way[i].v;
		bz[0][way[i].to] = x;
		dfs(way[i].to,x);
	}
}
inline void up(int & x,int y) {
	if(x < y) x = y;
}
inline int get(int x,int y) {
	if(dep[x] > dep[y]) std::swap(x, y);
	int ret = 0;
	for(int d = dep[y] - dep[x]; d; d &= d - 1) up(ret, max[__builtin_ctz(d)][y]), y = bz[__builtin_ctz(d)][y];
	for(int i = 19;i >= 0;--i) if(bz[x][i] != bz[y][i]) {
		up(ret, max[i][x]), x = bz[i][x];
		up(ret, max[i][y]), y = bz[i][y];
	}
	if(x != y) up(ret, std::max(max[0][x], max[0][y]));
	return ret;
}
int in[maxn];
int fa[maxn];
inline int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]); }
int n, m;
ll x, sum;
int main() {
	std::ios::sync_with_stdio(false), std::cin.tie(0);
	std::cin >> n >> m >> x;
	for(int i = 1;i <= n;++i) fa[i] = i;
	for(int i = 1;i <= m;++i) std::cin >> e[i].u >> e[i].v >> e[i].w;
	std::sort(e + 1,e + m + 1,[](const T & x,const T & y) { return x.w < y.w; });
	for(int i = 1;i <= m;++i) {
		if(find(e[i].u) != find(e[i].v)) {
			fa[find(e[i].u)] = find(e[i].v);
			sum += e[i].w;
			link(e[i].v, e[i].u, e[i].w);
			in[i] = 1;
		}
	}
	dfs(1);
	if(x < sum) {
		std::cout << 0 << '\n';
		return 0;
	}
	if(x == sum) {
		int cnt = 0;
		for(int i = 1;i <= m;++i) cnt += get(e[i].u, e[i].v) == e[i].w;
		std::cout << (pow(2, cnt) - 2) * pow(2, m - cnt) % mod << '\n';
		return 0;
	}
	int cnt0 = 0, cnt1 = 0;
	for(int i = 1;i <= m;++i) cnt0 += e[i].w - get(e[i].u, e[i].v) < x - sum;
	for(int i = 1;i <= m;++i) cnt1 += e[i].w - get(e[i].u, e[i].v) == x - sum;
	std::cout << 2 * (pow(2, cnt1) - 1) * pow(2, m - cnt0 - cnt1) % mod << '\n';
}

Submission Info

Judge Result