随猫与计数

题目描述

给定一棵以 $1$ 为根的树，对于每对 $(u,v)$，求下面问题的答案：

称长度不超过 $n$、值域为 $[1,n]$ 的序列 $p$ 是好的当且仅当：

• $p$ 中的元素两两不同；
• $u$ 和 $v$ 都在序列 $p$ 中；
• 若 $x,y$ 同时在序列 $p$ 中，且 $x$ 是 $y$ 的祖先，则 $x$ 在 $y$ 的前面。

求 $u$ 和 $v$ 在所有好的序列中的位置差的和，对 $10^9+7$ 取模。

输入格式

第一行一个整数 $n$，表示树的大小。

第二行 $n-1$ 个整数，第 $i$ 个整数 $p_{i+1}$ 表示 $i+1$ 的父亲。

输出格式

输出 $n$ 行每行 $n$ 个整数，第 $i$ 行第 $j$ 列的整数表示 $u=i,v=j$ 时的答案。

样例 1 输入

3
1 1

样例 1 输出

0 4 4
4 0 4
4 4 0

样例 2 输入

5
1 1 2 2

样例 2 输出

0 26 54 59 59
26 0 48 46 46
54 48 0 54 54
59 46 54 0 44
59 46 54 44 0

数据范围

对于所有数据，$1\le n\le150$，$1\le p_i\le i-1$。

评分方式

一个测试点的分数为：

• 若你输出的答案全部正确，并且输出格式正确，获得 $100$ 分。
• 否则若你输出的第一行答案正确，并且输出格式正确，获得 $20$ 分。
• 否则获得 $0$ 分。

对于一个子任务，你在这个子任务的得分为它以及它依赖的子任务中的测试点得分的最小值，乘以该子任务分值，再乘以 $\frac{1}{100}$。

子任务

本题采用捆绑测试，并开启所有合理的子任务依赖。

特殊性质 A：$p_i=i-1$。

特殊性质 B：$p_i=1$。

特殊性质 C：$p_i=\lfloor i/2\rfloor$。