题目
http://codeforces.com/contest/902/problem/B
题意分析
以第一个Example为例 第一行的数，表示结点数目为6 第二行的五个数，表示节点之间的关系
父节点12215
子节点23456
用图来表示
第3行的数，表示最终要涂成的每个节点的颜色
思路
要从上往下图，刚开始把根结点（即节点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;
}
更多内容请关注微信公众号
