# 我爱 STL，即使它慢

典型树上 DP。

思维难度比较大。

这题我们可以知道每一个人都至少自己做一次工作，

这次工作获得的金币为 1。

所以 $f[x] = 1$。

一个人的老板肯定比这个人收入多。

对于每次工作一个人的老板一定收入比助手多 1。

而一个人能参与的工作的次数，

就是他的助手数（包括助手的助手）。

我们令 $se[x]$ 表示x的助手数（包括助手的助手）。

那么 $f[x] += f[y] + se[y]$。

这样做时间空间复杂度都是 $O(n)$。

编程复杂度极低。

最后 AC 代码（ 30 行搞定）：

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
#define int long long
vector <int> a[N];
int n,se[N],f[N];
void build(int x){
    se[x] = 1;
    for(int i = 0;i < a[x].size();i++){
        build(a[x][i]);
        se[x] += se[a[x][i]];
    }
}
void dfs(int x){
    f[x] = 1;
    for(int i = 0;i < a[x].size();i++){
        dfs(a[x][i]);
        f[x] += f[a[x][i]] + se[a[x][i]];
    }
}
signed main(){
    scanf("%lld",&n);
    for(int i = 2,o;i <= n;i++){
        scanf("%lld",&o); 
        a[o].push_back(i);
    }
    build(1),dfs(1);
    for(int i = 1;i <= n;i++) printf("%lld ",f[i]);
    return 0;
}