AcWing 4490. 染色(dfs)
原题链接
困难
作者:
浅默淡殇
,
2022-07-02 21:52:04
,
所有人可见
,
阅读 272
dfs深搜,依次找到每个节点与父节点不相同的个数
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10;
int h[N], e[N], ne[N], color[N], idx;
int n, res = 0;
void add(int a,int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
void dfs(int u,int c)
{
if(color[u] != c) //和父节点颜色不同则res ++
res ++;
for(int i = h[u]; ~i;i = ne[i])
{
int j = e[i];
dfs(j, color[u]);
}
}
int main()
{
memset(h, -1, sizeof h);
cin >> n;
for(int i = 2;i <= n;i ++)
{
int j;
cin >> j;
add(j, i);
}
for(int i = 1;i <= n;i ++)
cin >> color[i];
dfs(1, 0);
printf("%d\n", res);
return 0;
}