# POI 2 Stage 2 Mudstock Bis ( Tree, DP )

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

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.

dis[ u ] : u 以下的所有節點的人，走到 u 的花費
cnt[ u ] : u 以下的所有節點的人 ( 包含 u )，一共有多少人

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;
}
```