ARC093 E - Bichrome Spanning Tree

AtCoder Regular Contest
問題

n頂点m辺の重み付き無向グラフと整数xが与えられる
このグラフの各辺を白or黒で塗る方法で、以下の条件を満たすものの個数を求める
条件: 白く塗られた辺と黒く塗られた辺をともに含む全域木が存在し、そのような全域木のうち最も重みが小さいものの重みはxである

1 <= n <= 1000
1 <= m <= 2000

解法

まず適当な最小全域木Tを見つけて、その重みをsとし、x-sをdifと呼ぶことにする
dif<0ならこの時点で答えは0 (その全域木をどういじっても重みがxを超えちゃうから)
dif>=0ならこの全域木をベースにして考える

2頂点u,vについて、T上のu,v間のパス上の辺の重みの最大値をmx[u][v]とすると、Tに含まれない辺e = {u,v}が存在しその重みがcであるとき、前者の辺を後者の辺で代用すると全域木Tの重みは c-mx[u][v] (=incとする)だけ増える
グラフの辺を白か黒で塗った時、白く塗られた辺と黒く塗られた辺を両方含む全域木のうち最小の重みのものの重みs'は、
Tに白黒両方の辺が含まれるとき) s' = s
そうでない場合) Tに含まれず、Tの辺と異なる色で塗られた辺のうち最小のincの値を持つものをeとして、s' = s + inc(e)

このことから求める値は、inc(e)=dif, inc(e)>difを満たすeの個数をそれぞれeq、upとすると
・dif=0のとき
Tの辺に白黒を両方使う場合、Tの辺n-1本の色は全て同じ色になる2通りを除けば何でもよく、残りm-(n-1)本も何でもいいから
(2^(n-1) - 2) * 2^(m-n+1) 通り
Tの辺はどっちか1色だけで塗る場合、その色が2通りあり、eq本の辺のうち1本以上はTと違う色で塗る必要があり、up本の辺はどうでもいいから
2 * (2^eq - 1) * 2^up 通り

・dif>0のとき)
Tの辺をどっちか1色だけで塗り、eq本の辺を1本以上はそれと違う色で塗り、up本はどうでもいい
2 * (2^eq - 1) * 2^up 通り

実装

クラスカル法で最小全域木Tに含まれる辺とTの重みを求める
→ Tに含まれる辺のみで木を作り(∴Tそのものの再構築)(辺の情報:ee)、rec()で任意の2頂点間のT上のパス上の辺の重みの最大値mx[u][v]を求める
→ Tに含まれない辺を見ていき、eqとupの個数を数える

#define int long long

int n, m, x, a, b, c, dif, eq, up, res, mx[1010][1010];
vector<pair<int,pair<int,int> > > e;
vector<pair<int,int> > ee[1010];
bool us[2020], vis[1010];

struct UF {
	vector<int> p;
	UF(int n) : p(n, -1) {};
	bool unite(int u, int v) {
		if ((u = find(u)) == (v = find(v))) return false;
		if (p[u] > p[v]) swap(u, v);
		p[u] += p[v]; p[v] = u;
		return true;
	}
	bool same(int u, int v) { return find(u) == find(v); }
	int find(int u) { return p[u] < 0 ? u : p[u] = find(p[u]); }
	int usize(int u) { return -p[find(u)]; }
};

int kruskal(int n, int m, vector<pair<int,pair<int,int> > > &e) {
	sort(e.begin(),e.end());
	UF uf(n);
	int res = 0;
	for (int i=0; i<m; ++i) {
		if (!uf.same(e[i].second.first, e[i].second.second)) {
			uf.unite(e[i].second.first, e[i].second.second);
			res += e[i].first, us[i] = 1;
		}
	}
	return res;
}

void rec(int v, int t, int p) {
	vis[v] = 1;
	mx[p][v] = t;
	each(i,ee[v]) if (!vis[i.first]) rec(i.first, max(t,i.second), p);
}

signed main() {
	cin >> n >> m >> x;
	rep(i,m) {
		cin >> a >> b >> c;
		a--, b--;
		e.push_back({c,{a,b}});
	}
	dif = x - kruskal(n,m,e);
	rep(i,m) if (us[i])
		ee[e[i].second.first].push_back({e[i].second.second,e[i].first}),
		ee[e[i].second.second].push_back({e[i].second.first,e[i].first});
	rep(i,n) memset(vis,0,sizeof(vis)), rec(i,0,i);
	rep(i,m) if (!us[i]) {
		int t = e[i].first - mx[e[i].second.first][e[i].second.second];
		if (t==dif) eq++;
		else if (t>dif) up++;
	}
	if (dif<0) res = 0;
	else if (dif==0) res = (mop(2,n-1)+mod-2) %mod *mop(2,m-n+1) + 2*(mop(2,eq)-1)*mop(2,up);
	else res = 2*(mop(2,eq)-1)*mop(2,up);
	res %= mod;
	cout << res << endl;
}

900点だけあって割と複雑だけど素直な考察で解ける方？
1個適当な最小全域木求めてそれをベースに考えていくみたいな問題何回か見てる気がする