#CF902B. 树染色
树染色
题目描述
给定一棵有 个节点的有根树,节点编号为 ,根节点为 。初始时所有节点的颜色均为 ,节点 的目标颜色为 。
每次操作可以选择一个节点 和一种颜色 ,将以 为根的整个子树中的节点染成颜色 。子树包括 本身,以及所有从根出发到它的简单路径经过 的节点。一次操作可以覆盖此前染上的颜色,操作可以执行任意多次。
请计算让所有节点达到目标颜色所需的最少操作次数。
输入格式
第一行输入一个整数 ,代表节点数量。
第二行输入 个整数 ,其中 是节点 的父节点。保证这些边构成一棵以节点 为根的树。
第三行输入 个整数 ,代表各节点的目标颜色。
输出格式
输出一个整数,代表完成目标染色所需的最少操作次数。
测试样例
6
1 2 2 1 5
2 1 1 1 1 1
3
样例 1 解释
先把整棵树染成颜色 ,再把以节点 为根的子树染成颜色 ,最后把以节点 为根的子树染成颜色 ,共需 次操作。根节点以及两个子树分别需要一次染色,因此无法少于 次。
7
1 1 2 3 1 4
3 3 1 1 1 2 3
5