풀이
트리에 존재하는 모든 노드에 대해,
각각의 노드에서 루트까지의 거리를 더하는 문제이다.
음… 그냥 짜면 된다.
코드
#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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이