[Acwing] 58周赛 4490. 染色

前言

周六的时候忙,听说这题挺难的,什么没见过的dp
结果感觉难度 C< B
$tag:$思维 树形结构
传送门 :

题意 :
给定一棵树和每个节点需要的颜色,你可以进行多次操作,询问最少的操作使得每个节点的颜色温和

操作定义如下 :

1. 选择一个节点 v 和一种颜色 x。

2. 将以节点 v 为根节点的子树中的全部节点（包括节点 v）都染成颜色 x。

思路 :
看完操作,很明显的就提示你了,是 自下而上的进行 $dfs$

然后我们再考虑怎么进行染色,显然我们可以贪心的考虑, 如果子树和本身颜色不同,显然是需要染色的

反之不需要染色, 这肯定是花费最小的(证明不知道,显然)

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 ;
}
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71