[acwing] 58 weeks 4490 dyeing

Preface

Busy on Saturday , It is said that this question is very difficult , What I haven't seen dp
The result feels difficult C< B
$tag:$ thinking A tree structure
Portal :

The question :
Given a tree and the color required for each node , You can do it many times , inquiry Minimal operation Make the color of each node mild

The operation is defined as follows :

1. Select a node v And a color x.

2. Will be in the form of nodes v All nodes in the subtree of the root node （ Including nodes v） All dyed in color x.

Ideas :
Read the operation , It clearly reminds you , yes Bottom up In the process of $dfs$

Then we will consider how to dye , Obviously we can Greedy consideration , If the subtree is different in color from itself , Obviously, it needs dyeing

On the contrary, there is no need to dye , It must be The least expensive ( Prove that you don't know , obviously )

Mycode :

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <queue>
#include <math.h>
#include <set>
#include <stack>
#include <algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false);
#define CIT cin.tie(0);
#define COT cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i<=b;i++)
#define Fde(i,a,b) for(int i=a;i>=b;i--)
#define cer(a) cerr<<#a<<'='<<(a)<<" @ line "<<__LINE__<<" "<<endl
typedef priority_queue<int,vector<int>,greater<int>>  Pri_m;
typedef pair<int,int> pii;
typedef vector<int> VI;
map<int,int> mp;
const int N = 2e5+10,INF = 0x3f3f3f3f;
const double eps = 1e-5;


struct node{
    
    int to,val;
};



vector<int> g[N];
int col[N];
int n,i;
int ans = 1;


void dfs(int u,int fa){
    

	for(auto x : g[u]){
    
		if(x == fa)continue;
		dfs(x,u);
		if(col[x] != col[u]) ++ ans;
	}
}
void solve(){
    
	cin>>n;
	Fup(i,2,n){
    
		int x;cin>>x;
		g[x].pb(i);
	}
	
	Fup(i,1,n) cin>>col[i];
	
	dfs(1,0);
	
	cout<<ans<<endl;
		
}

int main(){
    
	//int t;cin>>t;while(t--)
    solve();
    return 0 ;
}