天下一プログラマーコンテスト2016予選A: B - PackDrop

問題

B: PackDrop - 天下一プログラマーコンテスト2016予選A | AtCoder

解答

ある部分木の頂点とその親ノードとの間の辺Eで落とせるパケットは、部分木の全ての子に対しても共通に落とすことができる。辺Eで落とせる最大のパケットの量は、部分木の葉のの最小値である。

よって、葉から頂点の方向に最小値を取りながら落とすパケット量を決めつつ、根から実際にパケットを落としていくような方針が立つ。

実装の前に、一度サンプルを図示してアルゴリズムを確認する。

葉から取得できるコストに対して、コストの概念を拡張する。各ノードのコストは、自分を頂点とした部分木上のすべての頂点のコストの最小値とする。すると、(子ノードのコスト) - ( 親ノードのコスト) だけ、各辺にPackDropを配置すれば良いことがわかる。ただし、頂点0については親ノードが存在しないので、頂点0のコストは0とする。すべての辺について配置できるPackDropの総数が解となる。

int const inf = 1<<29;

map<int, int> cost;
vector<vector<int>> G;

int compute_cost(int curr) {
  int mn = inf;
  rep(i, G[curr].size()) {
    minimize(mn, compute_cost(G[curr][i]));
  }
  if (mn == inf && cost.find(curr) == cost.end()) { throw; }
  if (mn < inf) cost[curr] = mn;
  return cost[curr];
}

int main() {
  int N, M; cin >> N >> M;
  G.resize(N);
  vector<int> P(N); rep(i, N - 1) cin >> P[i + 1];
  rep(i, M) {
    int B, C; cin >> B >> C;
    cost[B] = C;
  }
  rep(i, N - 1) {
    G[P[i + 1]].push_back(i + 1);
  }
  compute_cost(0);
  cost[0] = 0;

  int64_t sum = 0;
  REP(i, 1, N) {
    sum += cost[i] - cost[P[i]];
  }
  cout << sum << "\n";
}