HourRank16 : C. Magic Number Tree

なんかまぐれ？で満点とれた。
https://www.hackerrank.com/contests/hourrank-16/challenges/james-tree

問題

N頂点の木を成す無向グラフが与えられる。
各辺には長さが設定されている。

ここで、N個の頂点を１つずつ取り除いていくことを考える。
頂点iを取り除く場合、iから連結した各頂点vに対する最短距離をすべて合算した上で、頂点iおよびiにつながる辺を取り除く。
上記合算値の総和を考える。

頂点の取り除き方はN!とおりの組み合わせがある。各組合せにおける上記合算値の総和を求めよ。

解法

２頂点U-Vをつなぐ長さLの辺が何回カウントされるかを考えよう。
U側にちかい頂点U'およびV側に近いV'に関し、U'またはV'を取り除く段階でこの辺がカウントされる条件を求めよう。

U'-V'間にはU',V'を含め(d(U,U')+d(V,V')+2)個の頂点がある。
これらの頂点のうち、U'またはV'のどちらかが最初に消されればよい。
よってそのような頂点対に対しを合算していけばよい。

実際はU',V'を列挙するとTLEしかねないので、d(U,U')が等しいU'やd(U,V')が等しいV'はまとめて処理するとよい。

ll pat[5050][5050];
int N;
vector<pair<int,int>> E[5050];
int C[5050];
int L[5050];
int R[5050];
ll ret;
ll mo=1000000009;
ll fact[5050],rev[5050];


void dfs(int cur,int pre,int d,int* V) {
	
	V[d]++;
	FORR(e,E[cur]) if(e.first!=pre) dfs(e.first,cur,d+1,V);
}

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y>>r;
		E[x-1].push_back({y-1,r});
		E[y-1].push_back({x-1,r});
	}
	
	fact[0]=1;
	for(i=1;i<=5005;i++) {
		fact[i]=fact[i-1]*i%mo;
		rev[i]=modpow(i);
	}
	
	FOR(i,N) FORR(r,E[i]) if(r.first<i) {
		ZERO(L);
		ZERO(R);
		dfs(i,r.first,1,L);
		dfs(r.first,i,1,R);
		
		for(x=1;L[x];x++) for(y=1;R[y];y++) {
			ret+=L[x]*R[y]*fact[N]%mo*2*rev[x+y]%mo*r.second%mo;
		}
		
	}
	
	cout<<ret%mo<<endl;
	
	
}

まとめ

辺のカウント回数を数える定番テク。