AcWing 4490. 染色
原题链接
困难
作者:
曦薇
,
2022-07-02 20:44:34
,
所有人可见
,
阅读 195
思路
- 因为对根节点染色会同时把它的子树上所有结点染色,所以染色顺序应该是从上往下的。
- 动态规划思想,一个根节点所在子树全部染好色需要的染色操作次数是它的所有孩子为根节点所在的子树操作数之和,如果某个孩子需要染上的色号和根结点相同,那么根节点染色后这么孩子也被染好色了,所以这个孩子所在的子树染色操作数减一。
- 时间复杂度为 $O(n)$ ,空间复杂度为 $O(n)$ 。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=20010;
vector<int> child[N];
int color[N];
int f[N];
int dfs(int node){
if(f[node]) return f[node];
int i;
int ans=0;
int flag=0;
for(i=0;i<child[node].size();i++){
int t=child[node][i];
if(color[t]==color[node]){
flag=1;
ans+=(dfs(t)-1);
}
else{
ans+=dfs(t);
}
}
ans++;
f[node]=ans;
//cout<<node<<" "<<f[node]<<endl;
return f[node];
}
int main(void){
int n,i;
scanf("%d",&n);
int t;
for(i=2;i<=n;i++){
scanf("%d",&t);
child[t].push_back(i);
}
for(i=1;i<=n;i++){
scanf("%d",&color[i]);
}
int ans=dfs(1);
cout<<ans<<endl;
return 0;
}
没必要这样写把(bushi