算法
dfs + 贪心
(发题解更容易以后找到, 佬们见谅)
直接建树, 然后贪心一下:
1. 如果不在第一步把根节点染色, 那么在根节点之前的操作都会被覆盖掉, 因此要先染根节点
2. 如果对于任意子树的根节点, 不先染这个根节点, 那么之前对于该根节点所接子树的操作也会被覆盖
3. 兄弟之间染色完全没有影响
综上: 答案就是 1 (根节点先染一次) + 与其子树根节点不同的节点数量, 所以先把ans置为 1
时间复杂度 $O(n)$
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int n, ans = 1;
int h[N], e[N], ne[N], idx;
int color[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u)
{
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (color[u] != color[j]) ans ++ ;
dfs(j);
}
}
int main()
{
scanf("%d", &n);
memset(h, -1, sizeof h);
for (int i = 2; i <= n; i ++ )
{
int p;
cin >> p;
add(p, i);
}
for (int i = 1; i <= n; i ++ ) scanf("%d", &color[i]);
dfs(1);
printf("%d\n", ans);
return 0;
}