UOJ Logo Universal Online Judge

UOJ

#33. 【UR #2】树上GCD

附件下载 统计

有一棵 $n$ 个结点的有根树 $T$。结点编号为 $1 \dots n$,其中根结点为 $1$。

树上每条边的长度为 $1$。我们用 $d(x,y)$ 表示结点 $x, y$ 在树上的距离,$\text{LCA}(x,y)$ 表示 $x, y$ 的最近公共祖先(即树中最深的既是 $v$ 的祖先也是 $u$ 的祖先的结点)。

对于两个结点 $u,v$ $(u\neq v)$,令 $a=\text{LCA}(u,v)$,定义 $f(u,v)=\gcd (d(u,a),d(v,a))$。其中 $\gcd(x,y)$ 表示 $x,y$ 的最大公约数,特别地, $\gcd(0,x)=\gcd(x,0)=x$ $(x\neq 0)$。

对于所有 $i \in \{1,2,\cdots,n-1 \}$,求出有多少对 $(u,v)$ $(u < v)$,满足 $f(u,v) = i$。

输入格式

输入第一行包含一个正整数 $n$。保证 $n \geq 2$。

第 $2$ 到 $n$ 行中,第 $i$ 行有一个正整数 $p_i$,表示结点 $i$ 在树上的父亲是 $p_i$。保证 $p_i < i$。

输出格式

输出共 $n-1$ 行,其中第 $i$ 行表示对于 $i$ 的答案。

C/C++ 输入输出 long long 时请用 %lld。C++ 可以直接使用 cin/cout 输入输出。

样例一

input

5
1
2
2
1

output

8
2
0
0

样例二

input

8
1
2
3
4
1
6
6

output

16
9
2
1
0
0
0

样例三

见样例数据下载。

限制与约定

测试点编号 $n$的规模 备注
1$n \leq 2000$$p_i$ 在 $\{1,2,\cdots,i-1\}$ 中均匀随机
2$n \leq 100000$
3$n \leq 200000$
4$n \leq 200000$除根结点外的每个结点至多拥有一个孩子
5$n \leq 200000$$p_i$ 在 $\max\{i - 10, 1\}$ 到 $i - 1$ 之间均匀随机
6$n \leq 50000$
7$n \leq 100000$
8$n \leq 150000$
9$n \leq 200000$
10$n \leq 200000$

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载