[JOI精進録] 難易度7「committee」(2008年日本情報オリンピック 春合宿1-1)
問題リンク
問題概要
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; }