AcWing 4490. 染色
原题链接
困难
作者:
cbh
,
2022-07-02 20:29:30
,
所有人可见
,
阅读 223
思路
其实挺简单的,代码不长
虽然我第T2没做出来,但这题真的水
容易想复杂 像我一开始一样(bushi
C++代码
思路是先把整个染成第一个的颜色
再顺着枝条染成小树根节点的颜色
以此类推。。。。。
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
struct edge{
int father;
int color;
}e[N];//结构体存方便
int n,cnt=0;
int main(){
cin>>n;
for(int i=2;i<=n;i++) cin>>e[i].father;
for(int i=1;i<=n;i++) cin>>e[i].color;
for(int i=n;i>1;i--)//倒序遍历,看看每一个节点跟自己的父节点颜色一不一样,不一样代表着父节点染色后需要染回来,所以cnt++
if(e[i].color!=e[e[i].father].color) cnt++;
cout<<cnt+1<<endl;//加上第一次染色~
return 0;
}