ICPCCamp 有 n 个商店,用 1,2,…,n 编号。对于任意 i>1,有从商店 pi 到 i 的单向道路。 同时,商店 i 出售类型为 ai 的商品。
Bobo 从商店 1 出发前往商店 i。他要在两个不同的商店购买商品(包括商店 1 和 i)。设他先购买的商品类型是 x,后购买的商品类型是 y,他用 fi 表示不同的有序对 ⟨x,y⟩ 的数量。 求出 f2,f3,…,fn 的值。
输入格式
输入文件包含多组数据,请处理到文件结束。
每组数据的第一行包含 1 个整数 n.
第二行包含 (n−1) 个整数 p2,p3,…,pn.
第三行包含 n 个整数 a1,a2,…,an.
输出格式
对于每组数据输出 (n−1) 个整数表示 f2,f3,…,fn.
样例输入
3 1 2 1 2 3 3 1 1 1 2 3 4 1 2 3 1 3 2 3
样例输出
1 3 1 1 1 3 5
样例解释
对于第三个样例,当 i=4 时,可能的有序对 ⟨x,y⟩ 有 ⟨1,2⟩,⟨1,3⟩,⟨2,3⟩,⟨3,2⟩,⟨3,3⟩ 共 5 种。所以 f4=5.
数据范围
- 1≤n≤105
- 1≤pi<i
- 1≤ai≤n
- n 的总和不超过 5×105.