대기업 승범이네 (백준 17831)

안녕하세요. 오늘은 멘토링을 해줄 겁니다.

문제

https://www.acmicpc.net/problem/17831

아이디어

dp[idx][0/1]: idx를 루트로 하는 서브트리에서의 정답의 최댓값: 0이면 idx를 포함 X, 1이면 포함 O
sum: 모든 자식들에 대해서 dp[그 자식][0]과 dp[그 자식][1]의 최댓값의 합입니다.

dp[node][0]은 쉽습니다. 그냥 sum입니다.
dp[node][1]은 조금 어려운데 특정한 자식과 자신을 이으려면 그 자식에서의 dp[그 자식][0]을 더하고 node*next를 더해주어야합니다. 또한 sum에서 그 자식은 정해졌으니 제외한 값인 sum-max(dp[그 자식][0],dp[그 자식][1])을 더해주면 됩니다.

소스코드

#include <iostream>
#include <vector>
#define ll long long
using namespace std;

ll skill[202020] = { 0 };
ll dp[202020][2] = { 0 };
vector <ll> v[202020];
void DFS(ll node)
{
    ll sum = 0; //전체를 다 상관없이 한 경우
    for (ll next : v[node])
    {
        DFS(next);
        dp[node][0] += max(dp[next][0], dp[next][1]);
        sum += max(dp[next][0], dp[next][1]);
    }
    for (ll next : v[node])
    {
        dp[node][1] = max(dp[node][1], sum - max(dp[next][0], dp[next][1]) + dp[next][0] + skill[node] * skill[next]);
        //전체-현재최대+현재 next값은 0 + skill곱
    }
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, i, x;
    cin >> N;
    for (i = 2; i <= N; i++)
    {
        cin >> x;
        v[x].push_back(i);
    }
    for (i = 1; i <= N; i++) cin >> skill[i];

    DFS(1);
    cout << max(dp[1][0], dp[1][1]);
}

감사합니다.