QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB
[0]

# 3748. 买一送一

统计

ICPCCamp 有 n 个商店,用 1,2,,n 编号。对于任意 i>1,有从商店 pii 的单向道路。 同时,商店 i 出售类型为 ai 的商品。

Bobo 从商店 1 出发前往商店 i。他要在两个不同的商店购买商品(包括商店 1i)。设他先购买的商品类型是 x,后购买的商品类型是 y,他用 fi 表示不同的有序对 x,y 的数量。 求出 f2,f3,,fn 的值。

输入格式

输入文件包含多组数据,请处理到文件结束。

每组数据的第一行包含 1 个整数 n.

第二行包含 (n1) 个整数 p2,p3,,pn.

第三行包含 n 个整数 a1,a2,,an.

输出格式

对于每组数据输出 (n1) 个整数表示 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,y1,2,1,3,2,3,3,2,3,35 种。所以 f4=5.

数据范围

  • 1n105
  • 1pi<i
  • 1ain
  • n 的总和不超过 5×105.