#CF902B. 树染色

树染色

题目描述

\hspace{15pt}给定一棵有 nn 个节点的有根树,节点编号为 1∼n1\sim n,根节点为 11。初始时所有节点的颜色均为 00,节点 ii 的目标颜色为 cic_i。

\hspace{15pt}每次操作可以选择一个节点 vv 和一种颜色 xx,将以 vv 为根的整个子树中的节点染成颜色 xx。子树包括 vv 本身,以及所有从根出发到它的简单路径经过 vv 的节点。一次操作可以覆盖此前染上的颜色,操作可以执行任意多次。

\hspace{15pt}请计算让所有节点达到目标颜色所需的最少操作次数。

输入格式

\hspace{15pt}第一行输入一个整数 n(2≦n≦104)n\left(2\leqq n\leqq10^4\right),代表节点数量。

\hspace{15pt}第二行输入 n−1n-1 个整数 p2,p3,…,pn(1≦pi<i)p_2,p_3,\dots,p_n\left(1\leqq p_i<i\right),其中 pip_i 是节点 ii 的父节点。保证这些边构成一棵以节点 11 为根的树。

\hspace{15pt}第三行输入 nn 个整数 c1,c2,…,cn(1≦ci≦n)c_1,c_2,\dots,c_n\left(1\leqq c_i\leqq n\right),代表各节点的目标颜色。

输出格式

\hspace{15pt}输出一个整数,代表完成目标染色所需的最少操作次数。

测试样例

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

样例 1 解释

\hspace{15pt}先把整棵树染成颜色 22,再把以节点 55 为根的子树染成颜色 11,最后把以节点 22 为根的子树染成颜色 11,共需 33 次操作。根节点以及两个子树分别需要一次染色,因此无法少于 33 次。

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