#P3696. 化合物
化合物
题目描述
给定一棵以 1 号点为根的树。对于两个不同的点 ,设它们到最近公共祖先的距离分别为 ,定义这一无序点对的值为 。对每个值统计对应点对的个数。
输入格式
第一行一个整数 。接下来 行,第 行给出点 的父节点编号,其中 。
输出格式
从 开始按顺序输出每个 对应的点对数,每行一个数,直到最后一个点对数非零的 。中间的零也要输出。若没有点对,输出一行 0。
样例
3
1
1
1
2
数据范围
,树的最大深度不超过 。
给定一棵以 1 号点为根的树。对于两个不同的点 u,v,设它们到最近公共祖先的距离分别为 du,dv,定义这一无序点对的值为 duxordv。对每个值统计对应点对的个数。
第一行一个整数 N。接下来 N−1 行,第 i−1 行给出点 i 的父节点编号,其中 i=2,…,N。
从 k=0 开始按顺序输出每个 k 对应的点对数,每行一个数,直到最后一个点对数非零的 k。中间的零也要输出。若没有点对,输出一行 0。
3
1
1
1
2
1≤N≤105,树的最大深度不超过 500。