AcWing 4490. 染色题解

题目描述

样例

输入:

6
1 2 2 1 5
2 1 1 1 1 1

输出

3

算法描述

思路

我们以样例为例讲讲思路。

如何确保dfs能顺利便利呢，我们可以使用链式前向星来存图(树)

C++代码

#include <iostream>                 //头文件
#include <cstring>
#include <algorithm>

using namespace std;

const int N=10010,M=20010;

struct Edge                             //链式前向星
{
    int to;
    int next;
}e[M];

int head[N],idx;

void add(int a,int b)                   //链式前向星加边
{
    idx++;
    e[idx].to=b;
    e[idx].next=head[a];
    head[a]=idx;
}

int n;
int co[N];                              //目标状态
int cco[N];                             //当前状态
int cnt;                                //结果

void DFS(int u,int father)              //深搜
{
    if(co[u]==cco[father])              //已经被其父节点染过色且正确
    {
        cco[u]=co[u];
    }
    else                                //重新染色
    {
        cco[u]=co[u];
        cnt++;
    }
    for(int i=head[u];i;i=e[i].next)    //递推
    {
        if(e[i].to==father)continue;
        int to=e[i].to;
        DFS(to,u);
    }
}

int main()
{
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        int fa;
        cin>>fa;
        add(i,fa);
        add(fa,i);
    }
    for(int i=1;i<=n;i++)cin>>co[i];
    cco[0]=0x80808080;                  //预处理
    DFS(1,0);
    cout<<cnt<<endl;
}