AtCoder ARC #093 : E - Bichrome Spanning Tree

今回出てたらD問題はFA取れてたけど、EFは解けてなかったので微妙な結果に終わってそう。
https://beta.atcoder.jp/contests/arc093/tasks/arc093_c

問題

N頂点M辺の無向グラフが与えられる。
このグラフは連結であり、かつ各辺eには重さW[e]が設定されている。

各辺を白黒２色で塗り分けたとする。
その時、白黒両方を最低１本は含む全域木の中で辺の重さの総和の最小値がXとなるような塗り分け方は何通りあるか。

解法

まず適当に全域木を作り、その重みの和をDとする。
その全域木がすでに白黒の辺を最低１個ずつ含むなら重みの和はやはりDである。
その全域木の全辺が同色の場合、別の色の辺を１つは加えないといけないため、重みの和が変化する。

U-V間を結ぶ全域木に含まれない辺Eについて考える。
もし全域木の全辺が同色の場合、この辺Eに逆の色を塗ると、全域木におけるパスU-V中の重み最大の辺を外し、代わりにこの辺Eを加えることで条件を満たす全域木を作れる可能性がある。
この差分をdiff(E) = W[E] - (パスU-V中の最大の重み)とする。
また、全域木に含まれない辺についてA=diff(E)==0となるEの数、B=diff(E)==X-Dとなる辺の数とする。

• X＜Dの場合、そのような全域木は構築できないので解は0
• D==Xの場合
  • 元々の全域木を成す辺が２色とも含む場合他の辺はどうなってもよい。このケースは(2^N-2)*2^(M-N-1)通り。
  • 元々の全域木を成す辺が全て同色の場合、diff(E)==0となる辺が１つでも逆の色を持てばよいので2*(2^A-1)*2^B通り。
• X＞Dの場合
  • 重みの総和をXとするには、元の全域木が構成されては困るので、それらの辺はすべて同色とする。
  • diff(E)=X-Dとなる辺があった場合、その辺Eを元の全域木に加えることで条件を満たせる可能性があるので、その辺は元の全域木と逆の色にすることを考える。
  • すると2*(2^A-1)*2^Bが解。

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;

int N,M;
int U[2020],V[2020],W[2020],T[2020];
vector<pair<int,int>> E[2020];
int D[1010][1010];
ll X;
ll p2[2020];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p2[0]=1;
	FOR(i,2010) p2[i+1]=p2[i]*2%mo;
	
	cin>>N>>M>>X;
	priority_queue<pair<int,int>> PQ;
	FOR(i,M) {
		cin>>U[i]>>V[i]>>W[i];
		U[i]--;
		V[i]--;
		E[U[i]].push_back({V[i],i});
		E[V[i]].push_back({U[i],i});
		PQ.push({-W[i],i});
	}
	
	ll S=0;
	while(PQ.size()) {
		x=PQ.top().second;
		PQ.pop();
		if(uf[U[x]]!=uf[V[x]]) {
			S+=W[x];
			uf(U[x],V[x]);
			T[x]=1;
		}
	}
	FOR(i,N) {
		FOR(x,N) D[i][x]=1<<30;
		D[i][i]=0;
		priority_queue<pair<int,int>> Q;
		Q.push({0,i});
		while(Q.size()) {
			int co=-Q.top().first;
			int cur=Q.top().second;
			Q.pop();
			if(D[i][cur]!=co) continue;
			FORR(e,E[cur]) {
				if(D[i][e.first]>max(co,W[e.second])) {
					D[i][e.first]=max(co,W[e.second]);
					Q.push({-D[i][e.first],e.first});
				}
			}
		}
	}
	
	ll DD=X-S;
	
	int eq=0,up=0;
	FOR(i,M) if(T[i]==0) {
		if(W[i]-D[U[i]][V[i]]==DD) eq++;
		if(W[i]-D[U[i]][V[i]]>DD) up++;
	}
	ll ret=0;
	if(DD>0) {
		ret=2*(p2[eq]+mo-1)*p2[up]%mo;
	}
	else if(DD==0) {
		ret=2*(p2[eq]+mo-1)*p2[up]%mo;
		ret+=(p2[N-1]+mo-2)*p2[M-N+1]%mo;
	}

	cout<<ret%mo<<endl;
	
	
}

まとめ

本番出てたらこれ解けてなさそう。