[Acwing] 58周赛 4490. 染色

前言

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

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

操作定义如下 :

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

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

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

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

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

Mycode :

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
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 cer(a) cerr