cf) 참고 https://blog.naver.com/pasdfq/222690427665

42 개포 아카데미에서 평가가 안잡혀서 마침 코드잼을 하길래 풀어보았다..
1,2,3 번은 풀었는데 4번을 풀다가 맞왜틀 과정을 겪고 빡쳐서 집에 왔다ㅎㅎㅎ
어제 저녘에 풀라고 했는데 스르륵 잠이 들어서 일어나보니 끝나있었넹 ㅎㅎㅋㅋㅋㅋㅋ

4 chain reactions

자식 중에서 가장 적은 합을 가진 chain 이 연결 되는 그리디 알고리즘...을 적용을 못했다... 구현하기도 넘 어려운거 같다...나같은 알린이 입장에서는....

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<long long> cost;
vector<int> child;
vector<int> check[100001];
long long ans;

long long dfs(int start)
{
    if (check[start].size() == 0)
        return cost[start];
    long long m = dfs(check[start][0]);
    for (int i = 1; i < check[start].size(); i++)
    {
        long long y = dfs(check[start][i]);
        if (y < m)
        {
            ans += m;
            m = y;
        }
        else
        {
            ans += y;
        }
    }
    return max(m, cost[start]);
}

int main(void)
{
    int t;
    cin >> t;
    for (int tc = 1; tc <= t; tc++)
    {
        int n;
        cin >> n;
        cost.clear();
        child.clear();
        cost.resize(n + 1);
        child.resize(n + 1);
        for (int i = 0; i < 100001; i++)
        {
            check[i].clear();
        }
        for (int i = 1; i <= n; i++)
        {
            cin >> cost[i];
        }
        for (int i = 1; i <= n; i++)
        {
            cin >> child[i];
        }

        for (int i = 1; i <= n; i++)
        {
            check[child[i]].push_back(i);
        }

        ans = 0;
        ans += dfs(0);
        cout << "Case #"
             << tc << ": " << ans << "\n";
    }
    return 0;
}