백준온라인 17831번 [대기업 승범이네] [C++]

www.acmicpc.net/problem/17831

17831번: 대기업 승범이네

---

나의 풀이

이 문제는 그리디 하게 풀 수 없다 어느 사원이 속하냐 안 속하냐는 다른 사원들의 값에도 효과를 미치기 때문에 

방향을 고려하여 문제를 풀어야 된다

트리로 되어있는 문제이기때문에 맨 아래 리프 노드 푸터 루트 노드까지 쭉 뭔가 정보를 가지고 올려다 주면 위에서 판별할 수 있지 않을까 생각을 하였다

 

그리고 자료구조를 구성하자면

\( dp[i][2]\) 를 로 생각을 해볼 수 있다.  

\( dp[i][0]\) == i번 사원이 멘토가 된 상황일 때 하위모든 트리들의 총 시너지 값

\( dp [i][1]\) == i번 사원이 멘토가 된 상황이 아닐 때 하위모든 트리들의 총 시너지 값

 

이렇게 i번 사원이 멘토가 됐을 때와 안됬을 때로 구분 해준 이유는

i번 위에 j사원이 있다고 할 경우 j사원의 입장에서는 i번과 멘토를 할 때와 i번이 아닌 (예를 들어 k?) 다른 사원과 멘토 관계를 가질 때 계산되는 총 시너지 값이 다르기 때문이다.

 

점화식

\( dp [i][1]\) =  sum of for j in i's child \(max( dp [j][1], dp [j][2])\) 

하위가 멘토든지 아니든지 i는 멘토가 될 생각이 아니기 때문에 최댓값으로 계산

 

\( dp [i][2]\) = max of for j in i's child \(dp [j][2]\) + 나머지 j의들의 sum of \(max( dp [j][1], dp [j][2])\)

소스

---

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vpii = vector<pii>;

vi p[200001];
int sell[200001];
pii go(int cur){
    if(p[cur].size()==0)
        return {0,0};
    vpii v;

    int firstMax = 0,secondMax = 0;
    for(auto x: p[cur]){
        v.push_back(go(x)); 
        secondMax+=max(v.back().first,v.back().second);
    }
    for(int i=0;i<v.size();i++){
        if(v[i].first > v[i].second)
            firstMax = max(firstMax , secondMax -v[i].first+v[i].second + sell[cur]*sell[p[cur][i]]);
        else{
            firstMax = max(firstMax , secondMax + sell[cur]*sell[p[cur][i]]);
        }
    }
    return {firstMax,secondMax};
}
int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,x;
    cin>>n;

    for(int i=2;i<=n;i++){
        cin>>x;
        p[x].push_back(i);
    }

    for(int i=1;i<=n;i++){
        cin>>sell[i];
    }

    auto ans = go(1);
    cout<<max(ans.first,ans.second);
}