← 返回题目列表

Codeforces · 902/B

B. 给树着色

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

给你一棵有 n 个顶点的有根树。顶点编号从 1 到 n,根为顶点编号 1。

每个顶点都有一种颜色,我们用 cv 来表示顶点 v 的颜色。最初 cv = 0。

您必须使用尽可能少的步骤将树着色为给定的颜色。在每一步中,您可以选择一个顶点 v 和一个颜色 x,然后将 v 子树中的所有向量(包括 v 本身)着色为颜色 x。换句话说,对于每个顶点 u,使得从根到 u 的路径经过 v,设置 cu = x。

保证您必须用不同于 0 的颜色对每个顶点进行着色。

您可以使用以下链接了解什么是有根树:https://en.wikipedia.org/wiki/Tree_(graph_theory)。

输入

第一行包含一个整数 n (2 ≤ n ≤ 104) — 树中的顶点数。

第二行包含 n - 1 个整数 p2, p3, ..., pn (1 ≤ pi < i),其中 pi 表示顶点 i 和 pi 之间有一条边。

第三行包含 n 个整数 c1, c2, ..., cn (1 ≤ ci ≤ n),其中 ci 是您应该为第 i 个顶点着色的颜色。

保证给定的图是一棵树。

输出

打印一个整数 - 将树着色为给定颜色所需执行的最少步骤数。

示例

输入 #1

6
1 2 2 1 5
2 1 1 1 1 1

输出 #1

3

输入 #2

7
1 1 2 3 1 4
3 3 1 1 1 2 3

输出 #2

5

注意

第一个样本中的树如图所示(数字是顶点索引):

第一步,我们将顶点 1 的子树中的所有顶点着色为颜色 2(数字就是颜色):

第二步,我们将顶点 5 的子树中的所有顶点着色为颜色 1:

第三步,我们将顶点 2 的子树中的所有顶点着色为颜色 1:

第二个样本中的树如图所示(数字是顶点索引):

第一步,我们将顶点 1 的子树中的所有顶点着色为颜色 3(数字就是颜色):

第二步,我们将顶点 3 的子树中的所有顶点着色为颜色 1:

第三步,我们将顶点 6 的子树中的所有顶点着色为颜色 2:

第四步,我们将顶点 4 的子树中的所有顶点着色为颜色 1:

第五步,我们将顶点 7 的子树中的所有顶点着色为颜色 3: