[백준] 15386 Birokracija

오~~래 잡고 있던 문제다.. 8시간만에 푼듯 ㅎㅎ

문제는 리프부터 루트까지 계속 1씩 증가시키며 값을 더해주고 

방금 본 리프는 삭제시킨다. 그리고 새롭게 리프가 된 노드를 보며 

반복한다. 루트까지~

그리고 각 노드의 최종값을 출력하는 문제다

처음에 dfs 20만번이 먼저 떠올랐지만 참았다 ㅎㅎㅎ

생각해보면 자식부터 쭉 올라오므로 자식의 값을 그대로 받고

나의 자식 수 만큼 더하면 된다..! 그리고 나 자신을 위해 기본값은 1로한다!

풀고나면 쉬운 문제..

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define ll long long
const int MAXN = 2e5 + 5;
vector<vector<int>> Graph;
int n,par[MAXN],child[MAXN];
ll ans[MAXN];
int c_dfs(int x) {
    int c = 0;
    for (int i = 0; i < Graph[x].size(); i++) {
        int next = Graph[x][i];
        if (next != par[x]) c += c_dfs(next);
    }
    child[x] = c;
    return c + 1;
}
void dfs(int x) {
    ans[x] = 1;
    for (int i = 0; i < Graph[x].size(); i++) {
        int next = Graph[x][i];
        if (next != par[x]) {
            dfs(next); ans[x] += ans[next];
        }
    }
    ans[x] += (ll)child[x];
}
int main() {
    scanf(" %d", &n);
    Graph.resize(n + 1);
    for (int i = 2; i <= n; i++) {
        int x; scanf(" %d", &x);
        Graph[i].push_back(x);
        Graph[x].push_back(i);
        par[i] = x;
    }
    c_dfs(1);
    dfs(1);
    for (int i = 1; i <= n; i++) printf("%lld ", ans[i]);
}