NC13249
黑白树
https://ac.nowcoder.com/acm/problem/13249
NC13249
题意
给你一棵树，每个节点上有一个值
，一开始树上所有节点均为白色，要求你每次选择一个白色节点染色，从该节点往根的链上小于
的均被染色，求最小染色次数为多少？
思路
DFS 贪心
首先叶子结点是一定要染色的，我们考虑如何返回的时候构造最优方案，我们维护两个数组。
回溯路径所能染色到的最远距离
无须染色所能染色到的最远距离
当的时候，意味着到该节点必须进行一次染色，此时不一定是选择该节点进行染色，可以选择回溯路径所能染色到的最远距离那个点进行染色。
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const ll maxn = 1e6 + 5;
const int N = 1e5 + 5;
int n,f[N],k[N],d[N],res;
vector<int>G[N];
void dfs(int x,int fa){
for(int i=0;i<G[x].size();i++){
int s=G[x][i];
dfs(s,x);
k[x]=max(k[x],k[s]-1);
d[x]=max(d[x],d[s]-1);
}
if(!d[x]) ++res,d[x]=k[x];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=2;i<=n;i++){
int x; cin>>x;
G[x].push_back(i);
}
for(int i=1;i<=n;i++){
cin>>k[i];
}
dfs(1,-1);
cout<<res<<'\n';
return 0;
} 
投递中国移动等公司6个岗位