15368 : Birokracija

풀이

트리에 존재하는 모든 노드에 대해,

각각의 노드에서 루트까지의 거리를 더하는 문제이다.

음… 그냥 짜면 된다.

코드

#include <cstdio>
int n, par[200002], cnt[200002];
long long ans[200002];
int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) scanf("%d", &par[i]);
    for (int i = n; i >= 1; i--) {
        ans[par[i]] += ++ans[i] + ++cnt[i];
        cnt[par[i]] += cnt[i];
    }
    for (int i = 1; i <= n; i++) printf("%lld ", ans[i]);
    return 0;
}
#include <cstdio>
#include <vector>
using namespace std;

int n;
long long ans[200002];
vector<int> gph[200002];

pair<long long, int> go(int now, int prv) {
	pair<long long, int> ret;
	ret.first = 1;
	for (int nxt : gph[now]) {
		if (nxt == prv) continue;
		auto r = go(nxt, now);
		ret.first += r.first;
		ret.second += r.second;
	}
	ret.first = (ret.first + ret.second);
	ret.second++;
	ans[now] = ret.first;
	return ret;
}

int main() {
	scanf("%d", &n);
	for (int i = 2, x; i <= n; i++) {
		scanf("%d", &x);
		gph[i].push_back(x);
		gph[x].push_back(i);
	}

	go(1, -1);
	for (int i = 1; i <= n; i++) printf("%lld ", ans[i]);

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-09-17 12:25

Read more posts by this author