← 返回题目列表

AtCoder · dwacon6th_final_d

D. 三个保险箱

中文机器翻译题面 查看原题

配点 : 1400 点

問題文

AtCoder 的办公室是 N 房间 N - 1 它有一个木结构,由一条书籍走廊连接。 走廊 i 是一个房间 V_i 和房间 i + 1 双向连接。

你在办公室 N 与房间不同 我们选择了 3 房间并安装了保险箱。 此外,每个房间 对于 v ,房间 计算 v 与安装每个保险箱的房间之间的距离,并找到中值。 已记录 M_v 。 但后来我忘了我把保险箱安装在哪个房间了。

办公室结构及各房间 v 的值 给出了 M_v 。 保险箱的不同可能位置 查找 3 房间对的数量。

另外,房间 x 和房间 y 是房间的距离 x 房间来自 这是用户移动到 y 时必须经过的最少走廊数。

制約

  • 3 \leq N \leq 100,000
  • 1 \leq V_i \leq i (1 \leq i \leq N - 1)
  • 1 \leq M_v \leq N - 1 (1 \leq v \leq N)
  • 所有输入值都是整数。

入力

输入是按以下格式从标准输入给出的。

N
V_1
V_2
\vdots
V_{N - 1}
M_1
M_2
\vdots
M_N

出力

打印答案。 求解


入力例 1

8
1
2
1
4
1
6
4
2
1
2
1
2
3
4
2

出力例 1

2

满足条件的房间集合为(房间 1, 部屋 3, 部屋 5)和(房间 1, 部屋 3, 部屋 8)的 有 2 件。


入力例 2

5
1
2
3
4
1
1
1
1
1

出力例 2

0