English · Original
Chinese · Translation
Formal · Original
You are given a rooted tree with _n_ vertices. The vertices are numbered from 1 to _n_, the root is the vertex number 1.
Each vertex has a color, let's denote the color of vertex _v_ by _c__v_. Initially _c__v_ = 0.
You have to color the tree into the given colors using the smallest possible number of steps. On each step you can choose a vertex _v_ and a color _x_, and then color all vectices in the subtree of _v_ (including _v_ itself) in color _x_. In other words, for every vertex _u_, such that the path from root to _u_ passes through _v_, set _c__u_ = _x_.
It is guaranteed that you have to color each vertex in a color different from 0.
You can learn what a rooted tree is using the link: [https://en.wikipedia.org/wiki/Tree_(graph_theory)](https://en.wikipedia.org/wiki/Tree_(graph_theory)).
## Input
The first line contains a single integer _n_ (2 ≤ _n_ ≤ 104) — the number of vertices in the tree.
The second line contains _n_ - 1 integers _p_2, _p_3, ..., _p__n_ (1 ≤ _p__i_ < _i_), where _p__i_ means that there is an edge between vertices _i_ and _p__i_.
The third line contains _n_ integers _c_1, _c_2, ..., _c__n_ (1 ≤ _c__i_ ≤ _n_), where _c__i_ is the color you should color the _i_\-th vertex into.
It is guaranteed that the given graph is a tree.
## Output
Print a single integer — the minimum number of steps you have to perform to color the tree into given colors.
[samples]
## Note
The tree from the first sample is shown on the picture (numbers are vetices' indices):
On first step we color all vertices in the subtree of vertex 1 into color 2 (numbers are colors):
On seond step we color all vertices in the subtree of vertex 5 into color 1:
On third step we color all vertices in the subtree of vertex 2 into color 1:
The tree from the second sample is shown on the picture (numbers are vetices' indices):
On first step we color all vertices in the subtree of vertex 1 into color 3 (numbers are colors):
On second step we color all vertices in the subtree of vertex 3 into color 1:
On third step we color all vertices in the subtree of vertex 6 into color 2:
On fourth step we color all vertices in the subtree of vertex 4 into color 1:
On fith step we color all vertices in the subtree of vertex 7 into color 3:
你被给定一棵包含 #cf_span[n] 个顶点的有根树。顶点编号从 #cf_span[1] 到 #cf_span[n]，根是编号为 #cf_span[1] 的顶点。
每个顶点有一个颜色，记顶点 #cf_span[v] 的颜色为 #cf_span[cv]。初始时 #cf_span[cv = 0]。
你需要用最少的步数将树染成给定的颜色。每一步，你可以选择一个顶点 #cf_span[v] 和一种颜色 #cf_span[x]，然后将 #cf_span[v] 的子树中所有顶点（包括 #cf_span[v] 自身）染成颜色 #cf_span[x]。换句话说，对于每一个顶点 #cf_span[u]，如果从根到 #cf_span[u] 的路径经过 #cf_span[v]，则设置 #cf_span[cu = x]。
保证你需要将每个顶点染成不同于 #cf_span[0] 的颜色。
你可以通过以下链接了解什么是有根树：https://en.wikipedia.org/wiki/Tree_(graph_theory)。
第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 104]) —— 树中顶点的数量。
第二行包含 #cf_span[n - 1] 个整数 #cf_span[p2, p3, ..., pn] (#cf_span[1 ≤ pi < i])，其中 #cf_span[pi] 表示顶点 #cf_span[i] 和 #cf_span[pi] 之间有一条边。
第三行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn] (#cf_span[1 ≤ ci ≤ n])，其中 #cf_span[ci] 是你应该将第 #cf_span[i] 个顶点染成的颜色。
保证给定的图是一棵树。
请输出一个整数 —— 将树染成给定颜色所需的最少步数。
第一个样例中的树如图所示（数字为顶点编号）：
第一步，我们将顶点 #cf_span[1] 的子树中所有顶点染成颜色 #cf_span[2]（数字为颜色）：
第二步，我们将顶点 #cf_span[5] 的子树中所有顶点染成颜色 #cf_span[1]：
第三步，我们将顶点 #cf_span[2] 的子树中所有顶点染成颜色 #cf_span[1]：
第二个样例中的树如图所示（数字为顶点编号）：
第一步，我们将顶点 #cf_span[1] 的子树中所有顶点染成颜色 #cf_span[3]（数字为颜色）：
第二步，我们将顶点 #cf_span[3] 的子树中所有顶点染成颜色 #cf_span[1]：
第三步，我们将顶点 #cf_span[6] 的子树中所有顶点染成颜色 #cf_span[2]：
第四步，我们将顶点 #cf_span[4] 的子树中所有顶点染成颜色 #cf_span[1]：
第五步，我们将顶点 #cf_span[7] 的子树中所有顶点染成颜色 #cf_span[3]：
## Input
第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 104]) —— 树中顶点的数量。第二行包含 #cf_span[n - 1] 个整数 #cf_span[p2, p3, ..., pn] (#cf_span[1 ≤ pi < i])，其中 #cf_span[pi] 表示顶点 #cf_span[i] 和 #cf_span[pi] 之间有一条边。第三行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn] (#cf_span[1 ≤ ci ≤ n])，其中 #cf_span[ci] 是你应该将第 #cf_span[i] 个顶点染成的颜色。保证给定的图是一棵树。
## Output
请输出一个整数 —— 将树染成给定颜色所需的最少步数。
[samples]
## Note
第一个样例中的树如图所示（数字为顶点编号）：第一步，我们将顶点 #cf_span[1] 的子树中所有顶点染成颜色 #cf_span[2]（数字为颜色）：第二步，我们将顶点 #cf_span[5] 的子树中所有顶点染成颜色 #cf_span[1]：第三步，我们将顶点 #cf_span[2] 的子树中所有顶点染成颜色 #cf_span[1]：第二个样例中的树如图所示（数字为顶点编号）：第一步，我们将顶点 #cf_span[1] 的子树中所有顶点染成颜色 #cf_span[3]（数字为颜色）：第二步，我们将顶点 #cf_span[3] 的子树中所有顶点染成颜色 #cf_span[1]：第三步，我们将顶点 #cf_span[6] 的子树中所有顶点染成颜色 #cf_span[2]：第四步，我们将顶点 #cf_span[4] 的子树中所有顶点染成颜色 #cf_span[1]：第五步，我们将顶点 #cf_span[7] 的子树中所有顶点染成颜色 #cf_span[3]：
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of vertices in a rooted tree, with root at vertex $ 1 $.
Let $ P = (p_2, p_3, \dots, p_n) $, where $ p_i \in \{1, \dots, i-1\} $, define the parent of vertex $ i $ for $ i = 2, \dots, n $.
Let $ C = (c_1, c_2, \dots, c_n) $, where $ c_i \in \{1, \dots, n\} $, be the target color of vertex $ i $.
Let $ T = (V, E) $ be the tree with $ V = \{1, 2, \dots, n\} $ and edges $ \{(i, p_i) \mid i = 2, \dots, n\} $.
**Constraints**
1. $ 2 \leq n \leq 10^4 $
2. $ 1 \leq p_i < i $ for all $ i = 2, \dots, n $
3. $ 1 \leq c_i \leq n $ for all $ i = 1, \dots, n $
4. Initially, all vertices have color $ 0 $.
**Objective**
Find the minimum number of operations required to transform the initial coloring (all 0s) into the target coloring $ C $, where each operation consists of selecting a vertex $ v $ and a color $ x $, and coloring the entire subtree rooted at $ v $ with color $ x $.
API Response (JSON)
{
"problem": {
"name": "B. Coloring a Tree",
"description": {
"content": "You are given a rooted tree with _n_ vertices. The vertices are numbered from 1 to _n_, the root is the vertex number 1. Each vertex has a color, let's denote the color of vertex _v_ by _c__v_. Initi",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF902B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "You are given a rooted tree with _n_ vertices. The vertices are numbered from 1 to _n_, the root is the vertex number 1.\n\nEach vertex has a color, let's denote the color of vertex _v_ by _c__v_. Initi...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "你被给定一棵包含 #cf_span[n] 个顶点的有根树。顶点编号从 #cf_span[1] 到 #cf_span[n]，根是编号为 #cf_span[1] 的顶点。\n\n每个顶点有一个颜色，记顶点 #cf_span[v] 的颜色为 #cf_span[cv]。初始时 #cf_span[cv = 0]。\n\n你需要用最少的步数将树染成给定的颜色。每一步，你可以选择一个顶点 #cf_span[v] 和一种...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ be the number of vertices in a rooted tree, with root at vertex $ 1 $. \nLet $ P = (p_2, p_3, \\dots, p_n) $, where $ p_i \\in \\{1, \\dots, i-1\\} $, define the ...",
"is_translate": false,
"language": "Formal"
}
]
}