Problem E. 染色
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Problem E. 染色
时间限制:1s
空间限制:256MB
题目描述
给定一个 \(n\) 个节点的树,节点编号为 \(1∼n\)。
\(1\) 号节点是树的根节点。
初始时,所有节点的颜色均为 \(0\)。
现在,你需要对该树进行重新染色,其中节点 \(i\) 的目标颜色为 \(c_i\)。
每次染色操作的具体流程如下:
选择一个节点 \(v\) 和一种颜色 \(x\)。
将以节点 \(v\) 为根节点的子树中的全部节点(包括节点 \(v\))都染成颜色 \(x\)。
请你计算,为了使得每个节点都被染成目标颜色,至少需要进行多少次染色操作。
输入格式
第一行包含整数 \(n\)。
第二行包含 \(n−1\) 个整数 \(p_2,p_3,…,p_n\),其中 \(p_i\) 表示节点 \(i\) 的父节点编号。
第三行包含 \(n\) 个整数 \(c_1,c_2,…,c_n\),其中 \(c_i\) 表示节点 \(i\) 的目标颜色。
保证输入给定图是一棵树。
输出格式
一个整数,表示最少所需的染色操作次数。
输入样例
6
1 2 2 1 5
2 1 1 1 1 1
输出样例
3
样例解释
将节点1染成颜色2,再将节点2和节点5染成颜色1,需要操作3次
数据范围
\(2 \leq n \leq 10^5,1 \leq p_i < i,1 \leq c_i \leq n\)。