なんかまぐれ?で満点とれた。
https://www.hackerrank.com/contests/hourrank-16/challenges/james-tree
問題
N頂点の木を成す無向グラフが与えられる。
各辺には長さが設定されている。
ここで、N個の頂点を1つずつ取り除いていくことを考える。
頂点iを取り除く場合、iから連結した各頂点vに対する最短距離をすべて合算した上で、頂点iおよびiにつながる辺を取り除く。
上記合算値の総和を考える。
頂点の取り除き方はN!とおりの組み合わせがある。各組合せにおける上記合算値の総和を求めよ。
解法
2頂点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; }
まとめ
辺のカウント回数を数える定番テク。