Pinely Round 5 : F. SubMST

Editorialよりコメント欄の解法の方がわかりやすいな。
https://codeforces.com/contest/2161/problem/F

問題

木を成すN頂点の無向グラフが与えられる。
このグラフの元に、N頂点の完全グラフを作ることを考える。
この完全グラフの辺の長さは、元の木における２点間の距離と一致することとする。

このグラフの空でない頂点の部分集合からなる誘導部分グラフにおけるMSTの総和を求めよ。

解法

以下EditorialではなくEditorialページのコメント欄にあった解法を参考にした。

ある頂点対の間の辺がMSTに含まれる確率を漏れなく考える。
頂点対の距離が奇数である場合を考える。
とするとその中点は、元の木を成すグラフのある辺の中心に相当することになる。

よって、元の木の辺を総当たりし、その辺の中央が、MSTにおける２点を結ぶ辺の中心に相当するものとみなして数え上げよう。
頂点対(u,v)を考えるとき、その中心に相当する点から見てu,vより近い点が部分集合に入らなければいいので、その確率を考えて行けばよい。

頂点対の距離が偶数の場合、u側とv側どちらかが1短いケースを同様に考えて行けばよい。

int T,N;
vector<int> E[5050];
int D[5050][5050];
const ll mo=1000000007;
ll p2[5050];

void dfs(int cur,int pre,int d,int id) {
	D[id][cur]=d;
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur,d+1,id);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p2[0]=1;
	FOR(i,5020) p2[i+1]=p2[i]*2%mo;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) E[i].clear();
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		FOR(i,N) dfs(i,i,0,i);
		ll ret=0;
		FOR(i,N) FORR(e,E[i]) if(i<e) {
			vector<pair<int,int>> A,B;
			FOR(j,N) {
				if(D[j][i]<D[j][e]) A.push_back({D[j][i],j});
				else B.push_back({D[j][e],j});
			}
			sort(ALL(A));
			sort(ALL(B));
			y=0;
			FOR(x,A.size()) {
				int d=A[x].first;
				int v=A[x].second;
				while(y<B.size()&&B[y].first<d-1) y++;
				for(k=y;k<B.size()&&B[k].first<=d+1;k++) {
					int d2=B[k].first;
					int v2=B[k].second;
					if(d==d2||(v<v2!=d<d2)) {
						(ret+=D[v][v2]*p2[N-2-x-k])%=mo;
					}
					
				}
			}
			
		}
		cout<<ret<<endl;
		
	}
}

まとめ

最初自分が考えた解法も、このコメント欄解法寄りだったな。
こっちの方がわかりやすい。