Description

首长NOI惨跪，于是去念文化课了。现在，他面对一道化学题。
这题的来源是因为在一个奇怪的学校两个化竞党在玩一个奇怪的博弈论游戏。这个游戏很蛋疼，我相信你们也没有兴趣听。
由于这个游戏涉及博弈论，因此化竞的同学就要求首长求一个类似SG函数的值。
他们手中有一种非常神奇的化合物，它的分子由N个原子组成（不要在意一个原子可能和及其多个原子成键这个细节）。这个分子构成一个树结构，1号分子为根。 若两个原子i、j到它们的最近公共祖先的距离分别是Li和Lj，定义它们的Aij值为：
Aij=Li xor Lj
题目要求对于每一个k(k∈N)，求出两两A值为k的原子对个数。

Input

第一行一个整数N。
接下来N-1行，每行一个整数p，第新亍的整数表示第i个原子的父亲为p。

Output

从K=0开始，第k+1行输出两两A值为K的原子对个数，输出到第一个不为零的数为止。

Sample Input

3
1
1

Sample Output

1
2

HINT

【数据规模与约定】
用h表示树结构分子的最大深度。
N<=10^5,H<=500

题目分析

想 在以点x为根的一棵树里 什么样的节点能把x当做lca？
一定是在x的不同儿子的子树里对吧
令dp[i][j]代表在i的子树里 和i距离为j的节点个数
因为树高很小 我们开一个a[i]的桶 记录异或出i的节点数
顺次枚举儿子，枚举深度计算答案 注意 在枚举完这个儿子之后再把这个子树里的点加到dp[i][j]里
时间复杂度O(跑得过)

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int dp[100010][530];
int f[100010];
int n,m;
int head[100010],to[100010],net[100010],fa[100010];
int tot,deep[100010],mx[100010];
void add(int x,int y)
{
    net[++tot]=head[x],to[tot]=y,head[x]=tot;
}
void dfs(int x)
{
    dp[x][0]++,mx[x]=deep[x];
    for(int i=head[x];i;i=net[i])
        {
            deep[to[i]]=deep[x]+1,dfs(to[i]);
            for(int j=0;j<=mx[x]-deep[x];j++)
                for(int k=0;k<=mx[to[i]]-deep[to[i]];k++) 
                        f[j^(k+1)]+=dp[x][j]*dp[to[i]][k];
            for(int j=1;j<=mx[to[i]];j++) dp[x][j]+=dp[to[i]][j-1];
            mx[x]=max(mx[x],mx[to[i]]);
        }
}
int main()
{
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
        scanf("%d",&fa[i]),add(fa[i],i);
    dfs(1);
    for(int i=0;f[i];i++) printf("%d\n",f[i]);
    return 0;
}