D - Three Safes /

Time Limit: 2.525 sec / Memory Limit: 1024 MB

配点 : 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