Coloring a Tree
题意翻译
一棵树根顶点编号为 $1$ 的树，每次可以选择一个子树染成同一个颜色，求染成目标状态的最小操作次数。
**【输入格式】**
- 第一行为一个整数 $n$。保证 $2 \le n \le 10^4$；
- 第二行 $p_2, p_3, \ldots, p_n$ 表示点 $i$ 和点 $p_i$ 之间有一条边。保证 $1 \le p_i < i$；
- 第三行 $c_i$ 表示点 $i$ 的目标颜色。保证 $1 \le c_i \le n$。
题目描述
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: <a>https://en.wikipedia.org/wiki/Tree\_(graph\_theory)</a>.
输入输出格式
输入格式
The first line contains a single integer $ n $ ( $ 2<=n<=10^{4} $ ) — 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.
输出格式
Print a single integer — the minimum number of steps you have to perform to color the tree into given colors.
输入输出样例
输入样例 #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
说明
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 $ :
