Bangladesh OI 2016 National Round pE. Village Fair ( Smaller to Larger )

http://codeforces.com/gym/101212/attachments/download/5014/bangladesh-informatics-olympiad-2016-en.pdf
Dashboard - Bangladesh Informatics Olympiad 2016 - Codeforces

題意：
有 N 個房子，一開始裡面都有一個小屁孩，用屁孩值描述。每個房子的出度都為 1，也就是都有一個有向邊向外連。但有個房子是例外，會連到自己，稱之為屁孩王國。保證每個房子恰好都存在一個簡單路徑可以達到屁孩王國。現在每個邊有一個屁孩 delta 值，走過去之後屁孩的屁孩值會 +delta。每個屁孩都走到屁孩王國。分別求每個房子看過幾種不同的屁孩值。

資料規模：
For easy version: 1≤ N≤ 1000. [30% of total score]
For hard version: 1≤ N≤ 100000. [100% of total score]
TL: 1000 ms
ML: 256 MB

解法：
把屁孩王國當做根，就是棵樹。所以 dfs，然後用啟發式合併，用 set< int > 管理當前房子會有的屁孩值。

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

注意：
如果 return pair< set< int >, int > 會 TLE = = 遞回函數一定要用 reference 傳值!!!!

int N;
vi J;
vi to;
vi delta;

void init(){
  cin >> N;
  J = to = delta = vi( N );
  for( int i = 0; i < N; ++i ){
    cin >> J[ i ];
  }
  for( int i = 0; i < N; ++i ){
    cin >> to[ i ];
    --to[ i ]; // to[ grand_house ] = -1
  }
  for( int i = 0; i < N; ++i ){
    cin >> delta[ i ];
  }
}

int grand_house = -1;
vvi from;
vi ans;

void dfs( int u, set< int > &cur, int &cur_add_all ){
  cur.emplace( J[ u ] );
  for( int v : from[ u ] ){
    pair< set< int >, int > vset;
    dfs( v, vset.first, vset.second );
    if( cur.size() >= vset.first.size() ){
      for( int x : vset.first ){
        x += vset.second + delta[ v ] - cur_add_all;
        cur.emplace( x );
      }
    } else{
      int p = cur_add_all;
      cur_add_all = vset.second + delta[ v ];
      swap( cur, vset.first );
      for( int x : vset.first ){
        x += p - cur_add_all;
        cur.emplace( x );
      }
    }
  }
  ans[ u ] = cur.size();
}

void preprocess(){
  from = vvi( N );
  ans = vi( N );
  for( int i = 0; i < N; ++i ){
    if( to[ i ] == -1 ){
      grand_house = i;
      continue;
    }
    from[ to[ i ] ].emplace_back( i );
  }
  set< int > _; int __ = 0;
  dfs( grand_house, _, __ );
}

void solve(){
  for( int i = 0; i < ans.size(); ++i ){
    cout << ans[ i ] << endl;
  }
}