Submission #9611757

---

Source Code Expand

#include <bits/stdc++.h>

const int mod = 1000000007;
const int MAXN = 200010;
typedef long long LL;
void reduce(int & x) { x += x >> 31 & mod; }
int pows[MAXN];
int n, m;
LL X;
int li[MAXN], bak;
int xs[MAXN], ys[MAXN], vs[MAXN];
bool prob[MAXN], realin[MAXN];
std::vector<int> es[MAXN];
namespace bingchaset {
	int fa[MAXN];
	void init(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }
	int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
}
int head[MAXN], nxt[MAXN << 1], to[MAXN << 1], val[MAXN << 1], tot;
void addedge(int b, int e, int v) {
	nxt[++tot] = head[b]; to[head[b] = tot] = e; val[tot] = v;
	nxt[++tot] = head[e]; to[head[e] = tot] = b; val[tot] = v;
}
int fa[17][MAXN], vt[17][MAXN], dep[MAXN];
void dfs(int u) {
	for (int i = 1; i != 17; ++i) {
		fa[i][u] = fa[i - 1][fa[i - 1][u]];
		vt[i][u] = std::max(vt[i - 1][u], vt[i - 1][fa[i - 1][u]]);
	}
	for (int i = head[u]; i; i = nxt[i])
		if (to[i] != fa[0][u]) {
			fa[0][to[i]] = u;
			vt[0][to[i]] = val[i];
			dep[to[i]] = dep[u] + 1;
			dfs(to[i]);
		}
}
int getminv(int x, int y) {
	int res = 0;
	if (dep[x] < dep[y]) std::swap(x, y);
	for (int i = dep[x] - dep[y]; i; i &= i - 1) {
		int t = __builtin_ctz(i);
		res = std::max(res, vt[t][x]);
		x = fa[t][x];
	}
	if (x == y) return res;
	for (int i = 16; ~i; --i)
		if (fa[i][x] != fa[i][y]) {
			res = std::max(res, std::max(vt[i][x], vt[i][y]));
			x = fa[i][x], y = fa[i][y];
		}
	res = std::max(res, std::max(vt[0][x], vt[0][y]));
	return res;
}
void solve() {
	std::cin >> n >> m >> X;
	for (int i = 1; i <= m; ++i)
		std::cin >> xs[i] >> ys[i] >> vs[i];
	memcpy(li, vs, m + 1 << 2);
	memset(realin, 0, m + 1);
	memset(prob, 0, m + 1);
	std::sort(li + 1, li + 1 + m);
	bak = std::unique(li + 1, li + 1 + m) - li - 1;
	for (int i = 1; i <= bak; ++i) es[i].clear();
	for (int i = 1; i <= m; ++i) {
		vs[i] = std::lower_bound(li + 1, li + 1 + bak, vs[i]) - li;
		es[vs[i]].push_back(i);
	}
	using bingchaset::find;
	bingchaset::init(n);
	int ccc = 0;
	LL sz = 0;
	for (int i = 1; i <= bak; ++i) {
		const int SZ = es[i].size();
		for (int j = 0; j != SZ; ++j) {
			int id = es[i][j];
			int x = xs[id], y = ys[id];
			if (find(x) != find(y)) prob[id] = true;
		}
		for (int j = 0; j != SZ; ++j) {
			int id = es[i][j];
			int x = xs[id], y = ys[id];
			if (find(x) != find(y)) {
				bingchaset::fa[find(x)] = find(y);
				realin[id] = true;
				sz += li[vs[id]];
				++ccc;
			}
		}
	}
	if (ccc != n - 1 || sz > X || n <= 2) {
		std::cout << 0 << std::endl;
		return ;
	}
	if (sz == X) {
		int cnt = 0;
		for (int i = 1; i <= m; ++i) cnt += prob[i];
		int ans = (LL) (pows[cnt] - 2) * pows[m - cnt] % mod;
		reduce(ans);
		std::cout << ans << std::endl;
		return ;
	}
	for (int i = 1; i <= m; ++i) if (realin[i])
		addedge(xs[i], ys[i], vs[i]);
	dfs(1);
	int cnx = n - 1, cny = 0;
	for (int i = 1; i <= m; ++i) if (!realin[i]) {
		int t = li[vs[i]] - li[getminv(xs[i], ys[i])];
		cnx += t < X - sz;
		cny += t == X - sz;
	}
	int ans = 2ll * (pows[cny] - 1) % mod;
	reduce(ans);
	ans = (LL) ans * pows[m - cnx - cny] % mod;
	std::cout << ans << std::endl;
	memset(head, 0, n + 1 << 2); tot = 0;
}
int main() {
	*pows = 1;
	for (int i = 1; i != MAXN; ++i)
		reduce(pows[i] = pows[i - 1] * 2 - mod);
	std::ios_base::sync_with_stdio(false), std::cin.tie(0); 
	solve();
	return 0;
}

Submission Info

Judge Result