PKU 3380 Bridges

http://poj.org/problem?id=3380

木が与えられる。k個のエッジでの移動速度を変更することができる。
このとき、全頂点間の移動コストの総和を最小にしたい。
移動速度を変更するk個のエッジを出力しろというような問題。

あるエッジの移動速度を変更したとき、その変更によって総コストがいくら変動するかは、エッジの両端から辿れる頂点数が求められれば求まる。
n本のエッジから辿れる頂点数をO(n)で求めればよい。

ゆとりな感じで書くと、時間がちょっと厳しいようです。

int n,k;
ll sh,sc;

vector<PI> G[10000];
bool vis[10000];

pair<ll,PI> so[100000];
int sos;

int dfs(int v){
  if(vis[v]) return 0;
  vis[v]=true;
  int ret=1;
  FOR(it,G[v]){
    ll tmp=dfs(it->F);
    if(tmp)
      so[sos++]=mp(-tmp*(n-tmp)*it->S*(sc-sh),mp(v,it->F));
    ret += tmp;
  }
  return ret;
}

main(){
  cin>>n>>k>>sh>>sc;
  map<PI,int> app;

  rep(i,n-1){
    int b,e,l;
    scanf("%d%d%d",&b,&e,&l);

    --b,--e;
    app[mp(b,e)]=i;
    app[mp(e,b)]=i;
    G[b].pb(mp(e,l));
    G[e].pb(mp(b,l));    
  }

  rep(i,n) if(SZ(G[i])==1){
    dfs(i);
    break;
  }

  sort(so,so+sos);
  rep(i,k) cout<<app[so[i].S]+1<<' ';
  cout<<endl;
}