POI 2 Stage 2 Mudstock Bis ( Tree, DP )

http://main.edu.pl/en/archive/oi/2/mud

題意：
首都在 ( 0, 0 ) 的位置，有 M 個人在首都裡。接著有 L 條線，每條線有若干個城市，依序用線上和前一個 ( 第一個城市和首都 ) 的距離以及人數描述。要求選一個點使得所有人到該點的總花費最小，一個人行走一單位距離的花費是一。

資料規模：
In the first line of the standard input there are two integers: the number of railway lines () and the number of the members living in the capital of the country ().
In the following lines of the file there are descriptions of the railway lines of successive numbers from to . Each description has a form of a sequence of integers separated by single spaces.
First, there is a positive number of settlements lying on the given line (not counting the capital). Each consecutive pair of numbers comprises: a positive distance of the successive settlement on the given line from the closest settlement towards the capital and a nonnegative number of the association's members living in this settlement. The last number of each description is directly followed by end-of-line character.

解法：
先將所有點映射成樹上的點。
一看就很有樹重心的感覺，用樹 dp 解決。
用一次 dfs 預處理：
dis[ u ] : u 以下的所有節點的人，走到 u 的花費
cnt[ u ] : u 以下的所有節點的人 ( 包含 u )，一共有多少人
在用一次 dfs 考慮所有節點是不是最優的即可。

時間 / 空間複雜度：
O( N )

#include <bits/stdc++.h>
using namespace std;

template< class T1, class T2 >
int upmin( T1 &x, T2 v ){
  if( x <= v ) return 0;
  x = v; return 1;
}

const int MAXL = 350;

int L, M;
vector< pair< int, int > > city[ MAXL ];

map< pair< int, int >, int > mp;
map< int, pair< int, int > > rmp;

int id( pair< int, int > p ){
  if( mp.count( p ) ) return mp[ p ];
  int size = mp.size();
  rmp[ size ] = p;
  return mp[ p ] = size;
}

vector< pair< int, int > > G[ MAXL * 100 + 1 ];
int cost[ MAXL * 100 + 1 ];

int dis[ MAXL * 100 + 1 ];
int cnt[ MAXL * 100 + 1 ];

void pre_dfs( int u, int fa ){
  cnt[ u ] = cost[ u ];
  for( int i = 0; i < G[ u ].size(); ++i ){
    int w = G[ u ][ i ].first, v = G[ u ][ i ].second;
    if( v == fa ) continue;
    pre_dfs( v, u );
    cnt[ u ] += cnt[ v ];
    dis[ u ] += dis[ v ] + cnt[ v ] * w;
  }
}

void dfs( int u, int fa, int up_cnt, int up_dis, int &ans, int &best ){
  if( upmin( ans, up_dis + dis[ u ] ) ){
    best = u;
  }
  for( int i = 0; i < G[ u ].size(); ++i ){
    int w = G[ u ][ i ].first, v = G[ u ][ i ].second;
    if( v == fa ) continue;
    int nc = up_cnt + cnt[ u ] - cnt[ v ];
    int nd = up_dis + dis[ u ] - dis[ v ] + ( nc - cnt[ v ] ) * w;
    dfs( v, u, nc, nd, ans, best );
  }
}

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> L >> M;
  cost[ id( make_pair( -1, -1 ) ) ] = M;
  for( int i = 0; i < L; ++i ){
    int size; cin >> size;
    for( int j = 0, prev = 0; j < size; ++j ){
      int d, w; cin >> d >> w;
      int c = id( make_pair( i, j ) );
      cost[ c ] = w;
      G[ prev ].push_back( make_pair( d, c ) );
      G[ c ].push_back( make_pair( d, prev ) );
      prev = c;
    }
  }
  int ans = 0x3f3f3f3f, best;
  pre_dfs( 0, -1 );
  dfs( 0, -1, 0, 0, ans, best );
  cout << ans << "\n";
  cout << rmp[ best ].first + 1 << " " << rmp[ best ].second + 1 << "\n";
  return 0;
}