UOJ Logo Universal Online Judge

UOJ

附件下载 统计

在到达了比特国 (Bitland) 后,伏特感受到了比特国当地特色的风土人情。

比特国的国土由 $n$ 座城市组成。城市的编号为 $1 \sim n$ 之间的整数。在城市之间修建了 $n-1$ 条无向的道路。其中第 $i$ ($1 \leq i \leq n-1$) 条道路连接了编号为 $i+1$ 与 $f_{i+1}$ 的城市 ($f_{i+1} < i+1$),且在道路上布置了一个类型为 $a_i$ 的展厅。为了便于居民的日常通行,任意两个城市之间都有且仅有一条简单路径连接这两座城市。换句话说,比特国的城市之间构成了一棵树。

比特国的传统节日“跳舞节”就要到来了!在跳舞节当天,比特国的国王字节王将会举办一场全国跳舞巡游活动。为了举办这次活动,字节王需要首先选择两个特殊的城市 $x, y$,并在这两座城市之间的唯一简单路径上举办庆典。在庆典举办期间,一辆比特跳舞车 (BitDance Car) 将会从起点城市 $x$ 出发,沿着唯一的简单路径前往终点城市 $y$。当比特跳舞车经过一条道路 $i$ 时,它会顺便前往道路上那个类型为 $a_i$ 的展厅并举办一次舞会。

在庆祝活动结束后,字节王会从这次举办的活动中选出一些高光时刻剪辑成回忆片。对于一次经过了城市 $v_1 \stackrel{e_1}{\longrightarrow} v_2 \stackrel{e_2}{\longrightarrow} \cdots \stackrel{e_{k-1}}{\longrightarrow} v_k$ 的巡游活动,字节王可以任意选择一组 $1 \leq i_1 < i_2 < \cdots < i_t \leq k-1$ ($t \ge 0$),并将比特跳舞车在经过 $e_{i_1}, e_{i_2}, \cdots, e_{i_t}$ 时所进行的舞会剪辑成回忆片,共全国的居民欣赏。

由于同样的回忆片被多次播放会导致大家感到无聊,因此字节王希望尽可能多的剪辑出不同的回忆片。我们称两个回忆片 $[e_1, e_2, \cdots, e_{m_1}]$ 与 $[e'_{1}, e'_{2}, \cdots, e'_{m_2}]$ 是不同的,当且仅当 $m_1 \ne m_2$,或存在一个 $1 \leq i \leq m_1$,使得 $a_{e_i} \ne a_{e'_{i}}$。即,把这两个回忆片按照顺序,将每条道路上举办的舞会的类型分别写成两个序列后,得到的两个序列不同。


在伏特出访比特国时,比特国的国王字节王向伏特诉说了自己的烦恼:每年在跳舞节举办后,字节王都尽可能地为大家准备了种类丰富的回忆片,但是在向市民播放完后,大家很快就忘记了这一年的活动,这让字节王感到很烦恼。

伏特很快发现,比特国的居民的大脑容量不足,只能记住一个比特!播放两个不同的回忆片,等于完全没有播放过!因此为了让所有居民能够记住每年举办的活动,字节王需要保证,它在这一年选择的起点城市 $x$ 和终点城市 $y$,能够使得最终恰好可以剪辑出奇数种不同的回忆片

分析到这里,伏特非常好奇,字节王能有多少种不同的方法,来举办出让所有居民都印象深刻的巡游活动呢?由于这个问题非常有趣,因此伏特希望你来帮助他与字节王来解决这个问题。

形式化题意:

给定一棵 $n$ 个点的树,每个点 $i$ ($1< i\leq n$) 和 $f_i$ 之间有一条无向边 ($f_{i} < i$),边权为 $a_i$。定义一个序列是好的,当且仅当它的本质不同子序列(包括空序列)个数为奇数。问有多少有序对 $(x,y)$ 使得 $x$ 到 $y$ 有向路径上的边权依次排成的序列是好的。

输入格式

第一行包含一个正整数 $n$。

第二行包含 $n-1$ 个正整数 $f_2,f_3,\cdots, f_{n}$,表示树上的边。

第三行包含 $n-1$ 个正整数 $a_2,a_3,\cdots, a_{n}$,表示边上展厅的类型。

输出格式

输出一行一个整数,表示答案。

样例一

input

4
1 2 2
2 1 1

output

6

explanation

合法的 $(x,y)$ 对有:$(1,1)$,$(2,2)$,$(3,3)$,$(4,4)$,$(3,4)$,$(4,3)$。

样例二

见附件下载。该样例满足子任务 4 的限制。

样例三

见附件下载。该样例满足子任务 7 的限制。

样例四

见附件下载。该样例满足子任务 8 的限制。

数据范围

对于所有数据,$2\leq n \leq 10^6$, $1\leq f_i < i$, $1\leq a_i < n$。

子任务编号 $n\leq $ 特殊性质 分值
$1$ $10^5$ A $5$
$2$ B $5$
$3$ $15$ $5$
$4$ $500$ C $20$
$5$ $5$
$6$ $5000$ $10$
$7$ $10^5$ $15$
$8$ $10^6$ C $10$
$9$ $25$

特殊性质 A:$a_i$ 互不相同。

特殊性质 B:$a_i=1$。

特殊性质 C:$f_i=i-1$。

提示:本题输入量较大,请使用较快的输入方法。

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

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