#P10498. [2021年联测]智慧树

    ID: 9615 传统题 1000ms 256MiB 尝试: 4 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-树形 DP小并大合并集合哈希表时间戳避免清空数组

[2021年联测]智慧树

题目描述

有一棵以 11 号节点为根的树。每个叶节点上有一个果实,所有果实的初始颜色均为 n+1n+1。给定每个果实所需的目标颜色,目标颜色属于 1,…,n1,\ldots,n。

一次操作选择一个节点及一种颜色,将该节点子树内所有叶节点的果实染成这个颜色。一个果实的颜色以最后一次染色为准,从未被染色的果实保持初始颜色。

求使所有果实达到各自目标颜色的最少操作数。

输入格式

第一行一个正整数 nn。第二行 n−1n-1 个整数 p2,…,pnp_2,\ldots,p_n,其中 pip_i 是节点 ii 的父节点。

第三行 nn 个整数 a1,…,ana_1,\ldots,a_n。对叶节点 ii,aia_i 表示其果实的目标颜色。对非叶节点,ai=0a_i=0。

输出格式

输出一个整数,表示最少染色次数。

样例 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

可以先把根的子树染成颜色 11,再分别把叶节点 55 和 77 染成颜色 22。原题另外在下发文件 wisdom3.in/out 与 wisdom4.in/out 中提供样例 3、4。

数据范围

所有数据满足 1≤n≤2×1051\le n\le 2\times10^5,0≤ai≤n0\le a_i\le n。

子任务 分值 附加限制
1 集合 {ai:1≤i≤n}\{a_i:1\le i\le n\} 的大小不超过 22
2 19 n≤9n\le9,答案不超过 33
3 45 n≤2×103n\le2\times10^3
4 35 n≤2×105n\le2\times10^5

原 PDF 题面