A - Coloring a Tree
题解：
先理解题意，给你n个点，代表这一棵树有n个节点。第二行内容是建树的关系。
1
2
| 例如：1 2 2 1 5
代表：节点2和节点1相连，节点3和节点2相连，节点4和节点2相连，节点5和节点1相连，节点6和节点5相连。
|
1
| 第三行内容是需要将各个点涂成的颜色，给这个树涂色，有这么一条原则就是给某一节点涂色，以其为根节点的子树也将变为相应的颜色。
|
思路：
1
2
3
| 因为最后需要使所有的点都涂成要求的颜色，一定是按照从根节点到叶子节点遍历的涂色，但所有的点都遍历会造成浪费，我们只需要找出需要涂的点即可，
那么哪些点需要涂呢？我们发现只有那些最后要求的其父亲节点和本身不同色的需要涂色，因为需要向下改变自身颜色，那么只需要统计这样点的个数即可。
最怕dfs因为dfs永远学不会，最后发现也可以直接循环搜索，反正都告诉你子节点父节点关系了，那就循环找呗。
|
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <iostream>
using namespace std;
int a[10000];
int b[10000];
int main()
{
int n,count=0;
cin>>n;
a[0]=1;a[1]=1;
for(int i=2;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
cin>>b[i];
}
for(int i=1;i<=n;i++)
{
if(b[i]!=b[a[i]])
{
count++;
}
}
cout<<count+1<<endl;
return 0;
}
|