[JOI精進録] 難易度7「committee」(2008年日本情報オリンピック 春合宿1-1)

問題リンク

atcoder.jp

問題概要

N人の人がいて、上下関係の木とそれぞれのやる気が渡される。
直接の関係を持つ人同士でしか連絡が取れないため、何人かを通して(通さなくてもよい)連絡が取れる人物を1人以上選出する。
また連絡の際中継する人物も入れなければならない。やる気の総和を最大化してください。

解説

AC解法 (100/100点)

木DPです。DFSをして子が正の数なら足していき、自分自身のやる気を更に足して更新します。

ACコード

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

int dfs(vector<vector<int>>& G,int d,vector<int>& A,int& r) noexcept {
  int dp = A[d],t;
  for (auto a:G[d]){
    t = dfs(G,a,A,r);
    if (t>0) dp+=t;
  }
  r = max(r,dp);
  return dp;
};

int main(){
  int r,n,a,b; cin >> n;
  vector<vector<int>> G(n); vector<int> A(n);
  for (int i(0);i < n;++i){
    (cin>>a>>b),A[i]=b;
    if (a==0) continue;
    G[a-1].emplace_back(i);
  }
  //assert(*max_element(A.begin(),A.end())>=0);
  r = *max_element(A.begin(),A.end());
  dfs(G,0,A,r);
  cout << r << endl;
}

提出結果

atcoder.jp