#P3696. 化合物

化合物

题目描述

给定一棵以 1 号点为根的树。对于两个不同的点 u,vu,v,设它们到最近公共祖先的距离分别为 du,dvd_u,d_v,定义这一无序点对的值为 duxordvd_u\mathbin{\mathrm{xor}}d_v。对每个值统计对应点对的个数。

输入格式

第一行一个整数 NN。接下来 N−1N-1 行,第 i−1i-1 行给出点 ii 的父节点编号,其中 i=2,…,Ni=2,\dots,N。

输出格式

从 k=0k=0 开始按顺序输出每个 kk 对应的点对数,每行一个数,直到最后一个点对数非零的 kk。中间的零也要输出。若没有点对,输出一行 0。

样例

3
1
1
1
2

数据范围

1≤N≤1051\le N\le10^5,树的最大深度不超过 500500。