题解 CF902B 【Coloring a Tree】

题面：一颗树，每次可以选择一个子树染成同一个颜色，求染成目标状态的最小操作次数。

首先，如果对于一个子树，这个子树的根节点需要被染色，那么这个根节点一定要先被染色，然后他的孩子们才会被染色。因为给这个根节点染色的时候，它下面的孩子们同时也会被染色，若是之前就给他的孩子们染色，那么这样的染色是会被浪费掉的。

其次，对于两个兄弟子树，他们染色的先后顺序是不影响染色的次数的。

知道的这两点之后，就有了一种很容易设计出的算法了。从根节点开始遍历整棵树，如果某个子树的根节点需要被染色，则ans++，并将这个子树染成这种颜色（打标记），然后再遍历它的所有孩子，重复以上操作。

代码（注释应该比较清晰）

#include<iostream>
using namespace std;
struct edge{
	int v,nxt;
}a[20005];
int head[10005],clr[10005],cnt=0;
void add_edge(int u,int v){
	cnt++;
	a[cnt].v=v;
	a[cnt].nxt=head[u];
	head[u]=cnt;
}//链式前向星
int dfs(int u,int color,int fa){//color代表它这个子树之前被染成什么颜色了，u是节点编号
	int ans=0;
	if(color!=clr[u])ans++;//需要被染色一次
	for(int i=head[u];i;i=a[i].nxt){
		if(a[i].v==fa)continue;
		ans+=dfs(a[i].v,clr[u],u);//递归下去，此时这个子树一定被染成了clr[u]这个颜色，因为如果没有将当前节点的子树染色，则这个子树一定在之前被染过一次色
	}
	return ans;
}
int main(){
	int n,v;
	cin>>n;
	for(int i=2;i<=n;i++){
		cin>>v;
		add_edge(i,v);
		add_edge(v,i);
	}
	for(int i=1;i<=n;i++)cin>>clr[i];
	cout<<dfs(1,0,-1);
	return 0;
}