题目内容

小蓝所在的公司有 $n$ 个部门，部门之间存在严格的上下级关系。$1$ 号部门是最高决策部门，其余每个部门有唯一的直接上级部门，整体构成一棵以 $1$ 号部门为根的层级结构，且每个部门至多有两个直接下级部门。

每个部门都有一个运算类型：类型 $1$ 表示该部门为“求和型”，类型 $2$ 表示该部门为“异或型”。现在需要从底层部门开始，逐级向上汇报一个汇报值，汇报规则如下：

• 若某部门没有任何下级部门，其汇报值固定为 $1$；
• 若某部门有且仅有一个下级部门，其汇报值等于该下级部门的汇报值；
• 若某部门有两个下级部门，则根据其类型计算：求和型部门的汇报值为两个下级部门汇报值的和；异或型部门的汇报值为两个下级部门汇报值的按位异或（用 $\oplus$ 表示）。

按位异或运算 $\oplus$ 定义在整数的二进制表示上，对应位不同时结果为 $1$，否则为 $0$。

给定所有部门的上级关系和运算类型，请你计算 $1$ 号部门最终的汇报值。

数据范围：部门总数 $n$ 满足 $2 \le n \le 50000$。保证上级关系合法，类型为 $1$ 或 $2$，且每个部门至多有两个下级部门。

输入描述

第一行包含一个整数 $n$ $(2 \le n \le 50000)$，表示部门的数量。 第二行包含 $n-1$ 个整数，依次表示部门 $2,3,\dots,n$ 的直接上级部门的编号。保证上级编号在 $1$ 到 $n$ 之间且构成合法层级关系，$1$ 号部门为根。 第三行包含 $n$ 个整数，第 $i$ 个整数 $t_i$ 表示部门 $i$ 的运算类型：$1$ 代表求和型，$2$ 代表异或型。

输出描述

输出一行一个整数，表示 $1$ 号部门最终汇报的汇报值。

样例1

输入

2
1
1 2

输出

1

说明

部门 2 为叶子部门，没有下级，汇报值固定为 1。部门 1 的类型为 1（求和型），但它只有一个下级部门 2，根据规则其汇报值等于下级部门的汇报值，因此最终汇报值为 1。

样例2

输入

3
1 1
1 2 2

输出

2

说明

部门 2 和部门 3 均为叶子部门，汇报值各为 1。部门 1 类型为 1（求和型），且有两个下级部门，因此汇报值为两个下级汇报值之和：$1 + 1 = 2$。

样例3

输入

4
1 2 2
2 1 2 2

输出

2

说明

部门 3 和部门 4 为叶子部门，汇报值均为 1。部门 2 类型为 1（求和型），有两个下级，汇报值为 $1 + 1 = 2$。部门 1 类型为 2（异或型），仅有一个下级部门 2，汇报值等于下级的值 2，等价于 $0 \oplus 2 = 2$。因此最终结果为 2。

样例4

输入

5
1 1 2 2
2 1 1 1 2

输出

3

说明

部门 4 和部门 5 为叶子部门，汇报值均为 1。部门 2 类型为 1（求和型），有两个下级，汇报值为 $1 + 1 = 2$。部门 3 为叶子部门，汇报值为 1。部门 1 类型为 2（异或型），有两个下级部门 2 和 3，其汇报值分别为 2 和 1，异或计算为 $2 \oplus 1 = 3$（二进制 10 与 01 按位异或得 11，即 3）。最终汇报值为 3。