Codeforces 101 D. Castle

問題

重み付き無向木が与えられる。
木のそれぞれのノードには宝が埋まっている。

ノード1から出発して、グラフの全部のノードを辿るように探索し、宝の埋まっているノードにたどり着いた瞬間に宝をする。
ただし、同じ辺は2度までしか通ることができない。

最適な順序でノードを辿ったときの宝の発見までの時間の期待値を求めよ。

制約条件

n≦10^5

方針

ノードv以下の全てのノードを辿って戻ってくるのにかかる時間をsum[v]
ノードvを出発して、vの子ノードを全て辿ったときに宝の発見時間に合計される値をdp[v]とする。

vの子ノードについて全てsumとdpが求まっているとき、
子ノードをどう辿るのが最善であるか。
例えばvには3つの子c1,c2,c3があって、c1→c2→c3の順に訪問するとする。
すると、宝の発見時間に合計される値は、
d[v][c1]*cld[c1] + dp[c1] + (2*d[v][c1]+sum[c1])*(cld[c2]+cld[c3]) + d[v][c2]*cld[c2] + dp[c2] + (2*d[v][c2]+sum[c2])*cld[c3] + d[v][c3]*cld[c3] + dp[c3]
のような形になることがわかる。
ここで、c2とc3の訪問順序を入れ替えると、
差分は(2*d[v][c2]+sum[c2])*cld[c3]-(2*d[v][c3]+sum[c3])*cld[c3]になる。

すなわち、辺を(2*d[v][c]+sum[c])/cld[c]の順にソートしてやれば、最適になることがわかる。

ソースコード

int n;
vector<vector<pi> > g;
double dp[100000],sum[100000];
int cld[100000];

bool cmp(pair<pair<double,double>,pi> a,pair<pair<double,double>,pi> b){
  return a.first.first*b.first.second<b.first.first*a.first.second;
}
void rec(int c,int p){
  double res=0;
  vector<pair<pair<double,double>,pi> > v;
  cld[c]=1;
  rep(i,g[c].size()){
    int to=g[c][i].first, cost=g[c][i].second;
    if(to==p)continue;
    rec(to,c);
    sum[c]+=cost*2+sum[to];
    cld[c]+=cld[to];
    v.pb(mp(mp(sum[to]+cost*2,cld[to]),mp(to,i)));
  }
  sort(all(v),cmp);
  int num=cld[c]-1;
  rep(i,v.size()){
    int to=v[i].second.first, cost=g[c][v[i].second.second].second;
    if(to==p)continue;
    num-=cld[to];
    res+=dp[to]+cld[to]*cost+(cost*2+sum[to])*num;
  }
  dp[c]=res;
}

void run(){
  cin>>n;
  g.resize(n);
  rep(i,n-1){
    int a,b,c; cin>>a>>b>>c;
    g[--a].pb(mp(--b,c));
    g[b].pb(mp(a,c));
  }
  rec(0,-1);
  printf("%.9f\n",dp[0]/(n-1));
}