回答日:2021-10-01

質問する

質問リンク:https://www.acmicpc.net/problem/14267

アクセスと解析

これはあまり難しくないDFS問題のようです.
入力を受けると同時に、褒められた人は褒められた程度を保存します.
すべての入力を受け取った後、1番ノード(ボス)からDFSで自分が受け取った称賛を下の人に加えます.

コード#コード#

// 백준 14267번 : 회사 문화 1
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

vector<int> org[100001];
int dp[100001];

void dfs(int node) {
    for (int i = 0; i < org[node].size(); i++) {
        int next = org[node][i];
        dp[next] += dp[node];
        dfs(next);
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    
    int r;
    for (int i = 0; i < n; i++) {
        int root;
        cin >> root;
        org[root].push_back(i + 1);
    }
    
    for (int i = 0; i < m; i++) {
        int node, score;
        cin >> node >> score;
        dp[node] += score;
    }
    dfs(1);
    
    for (int i = 0; i < n; i++) {
        cout << dp[i + 1] << ' ';
    }
    
    return 0;
}

結果

フィードバック

DFSは解くたびに難易度に関係なく解けるようになりましたが….
もう一度練習するしかない.