#P10498. [2021年联测]智慧树
[2021年联测]智慧树
题目描述
有一棵以 号节点为根的树。每个叶节点上有一个果实,所有果实的初始颜色均为 。给定每个果实所需的目标颜色,目标颜色属于 。
一次操作选择一个节点及一种颜色,将该节点子树内所有叶节点的果实染成这个颜色。一个果实的颜色以最后一次染色为准,从未被染色的果实保持初始颜色。
求使所有果实达到各自目标颜色的最少操作数。
输入格式
第一行一个正整数 。第二行 个整数 ,其中 是节点 的父节点。
第三行 个整数 。对叶节点 , 表示其果实的目标颜色。对非叶节点,。
输出格式
输出一个整数,表示最少染色次数。
样例 1
7
1 1 2 2 3 3
0 0 0 1 1 1 2
2
样例 2
7
1 1 2 2 3 3
0 0 0 1 2 1 2
3
可以先把根的子树染成颜色 ,再分别把叶节点 和 染成颜色 。原题另外在下发文件 wisdom3.in/out 与 wisdom4.in/out 中提供样例 3、4。
数据范围
所有数据满足 ,。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 集合 的大小不超过 | |
| 2 | 19 | ,答案不超过 |
| 3 | 45 | |
| 4 | 35 | |