Description

没头脑是一家大公司的CEO。该公司由N人组成，编号为1到N，没头脑编号为1。每个员工（没头脑除外）都有一个老板，我们说这个员工是该老板的助手。每个老板都可以有多名助手。没头脑没有老板，但有他的助手。
之后会有一些任务，没头脑会将该任务委托给他编号最小的助手。然后，该助手也将任务委托给他编号最小的助手，并且这个过程重复进行，直到任务被发送给没有助手的人，然后他必须亲自完成任务。
执行任务的人获得1个硬币，那个人的老板获得2个硬币，老板的老板获得3个硬币，依此类推，一直到没头脑。之后，真正完成工作的员工意识到系统的不公平并感到伤心，并且不会再执行任务（也就是辞职）。
当公司收到的下一个任务时，因为少了一个人，所以薪水可能更少，但工作必须继续。任务是无限多的（直到公司倒闭），因此整个过程（分配新任务，执行任务，划分薪水和执行任务人员的退出）重复进行，最后没头脑独自留在公司并完成他的第一个（也是他的最后一个）任务。
当然，在此之前，没头脑将积累相当多的财富，但他也想知道每个员工赚了多少钱。

Input

第一行有一个整数N，包括没头脑在内的员工的个数。
第二行有n-1个整数，分别为a2,a3,⋯,an，依次表示编号2,3,4,..n的员工的老板。

Output

输出一行N个整数，第i个整数表示编号为i的人获得的硬币数量。

Sample Input

【样例1输入】

3
1 1

【样例2输入】

5
1 2 2 4

Sample Output

【样例1输出】

5 1 1

【样例2输出】

13 8 1 3 1

HINT

对于50%的数据，2<=N<=5000。
对于100%的数据，2<=N<=2*10^5。

思路：

算是一道树形dp的题目，我们很容易发现这个人 u的工资是他的所有直接下属的工资和再加上他的下属的人数+1，我们用size[u]来表示他的下属人数，ans[u]代表他的工资，size[u] = 1 + ∑size[v],ans[u] = 1 + ∑(ans[v] + size[v])。

AC code:

#include<bits/stdc++.h>
using namespace std;
#define int long long//记得开long long
int size[200005];他的下属人数
int ans[200005];他的工资
vector<int>road[200005];
void dfs(int u)
{
   ans[u] = 1;
   size[u] = 1;
   for(int i = 0;i < road[u].size();i++)
   {
   	int v = road[u][i];
   	dfs(v);
   	size[u] += size[v];
   	ans[u] += ans[v] + size[v];
   }
}
signed main(){
   int n;
   scanf("%lld",&n);
   for(int i = 2;i <= n;i++)
   {
   	int fa;
   	scanf("%lld",&fa);
   	road[fa].push_back(i);//i是fa的直接下属
   }
   dfs(1);//从1也就是更节点开始
   for(int i = 1;i <= n;i++)
   {
   	printf("%lld ",ans[i]);
   }
   return 0;
}