小朋友学Codeforces（3）：Round 453 DIV 2, B

素颜马尾好姑娘i 2022-05-31 09:42 129阅读 0赞

## 题目 ##

[http://codeforces.com/contest/902/problem/B][http_codeforces.com_contest_902_problem_B]

## 题意分析 ##

以第一个Example为例  
第一行的数，表示结点数目为6  
第二行的五个数，表示节点之间的关系

用图来表示

![1.png][]

第3行的数，表示最终要涂成的每个节点的颜色

![2.png][]

## 思路 ##

要从上往下图，刚开始把根结点（即节点1）涂成C2，这样整棵树的颜色都是C2。  
接下来把节点2涂成C1色，节点3和节点4也自动变为C1色。  
最后把节点5涂成C1色，节点6也自动变成C1色。  
当然也可以按节点1–>节点5–>节点2的顺序来涂，即子树的顺序任意，效果一样。  
总共需要3步。

本题可通过深度优先搜索算法来实现。

## 代码 ##

#include <bits/stdc++.h>
    using namespace std;
    
    #define MAX 10001
    
    int c[MAX];
    bool visited[MAX];
    vector<int> adjvex[MAX];
    
    int ans = 1;
    
    void dfs(int v)
    {
        visited[v] = true;
        for (int i = 0; i < adjvex[v].size(); i++) 
        {
            int u = adjvex[v][i];
            if (!visited[u]) 
            {
                if (c[u] != c[v]) 
                {
                    ans++;
                }
                dfs(u);
            }
        }
    }
    
    int main()
    {
        int n;
        scanf("%d", &n);
        for (int i = 2; i <= n; i++) 
        {
            int p;
            scanf("%d", &p);
            adjvex[i].push_back(p);
            adjvex[p].push_back(i);
        }
    
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &c[i]);
        }
    
        dfs(1);
        printf("%d\n", ans);
    
        return 0;
    }

> 更多内容请关注微信公众号  
> ![wechat.jpg][]

[http_codeforces.com_contest_902_problem_B]: http://codeforces.com/contest/902/problem/B
[1.png]: /images/20220531/4371eb9190b649ef88611bad5fea5817.png
[2.png]: /images/20220531/31d9827746924704b51684ef37d147bf.png
[wechat.jpg]: /images/20220531/712dd62066824c65bf2bbdd6d48968f4.png